boj 128651 BOJ 12865 - 평범한 배낭 기본 knapsack문제다. int knapsack(int pos, int cap) // 가방의 남은 용량이 cap이고 pos~n-1번 물건을 고를 때 가치의 최대. 0번 물건~ n-1번 물건을 순서대로 참조하면서 1. pos번째 물건을 선택할 수 있을 경우 (물건의 무게가 cap보다 낮거나 같은 경우) ret = max(pos번째 물건을 선택하지 않은 경우, pos번째물건의 가치 + knapsack(pos+1, cap - item[pos].first) 2. pos번째 물건이 너무 무거워 선택할 수 없는 경우 ret = pos번째 물건을 선택하지 않은 경우 d[pos][cap]을 메모하며 dp하는 문제다. #include #include #include using namespace std; int n, .. 2019. 7. 29. 이전 1 다음