Slowly, Step by Step

Branch and Bound Similar to “Backtracking” - a state-space tree is used to solve a problem (pruning tree 사용한다) Different from “Backtracking” - does not limit us to any particular way of traversing a tree (탐색하는데에, 방법제한이 없다.) (backtrack에서는 recursion기반의 dfs가 중점적이다) - is used only for optimization problems (bound값을 사용해야해서, 최적문제들만 사용가능함) Step 1 computes a number (bound) at a node to determine whether..

문제 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 문제 풀이 #include using namespace std; int n, k; int w[100001] = { 0, }; int v[1001] = { 0, }; int dp[101][100001] = { 0, }; int main() { //물품의 수 N과 준서가 버틸수있는 무게 K주어진다 //두번째 줄부터, N개의 줄에 거쳐 각 물건의 무게 W와 해당 물건의 가치V가 주어진다 cin >>..

Backtracking greedy처럼 일련의 집합을 만들어 하나씩 답에 만족시키는 것을 만든다. greedy와 다르게, 조건에 맞지 않는다면 번복할 수 있다. 되돌아갈 수 있다. - used to solve problems in which a sequence of objects is chosen from a specified set so that the sequence satisfies some criterion. - after each choice has been made and added to a partial solution, it can be retracted from the solution set later by backtracking 5.1 The Backtracking Technique N..