배낭 문제 (Knapsack Algorithm) (Incomplete)

Knapsack Algorithm

---

0/1 Knapsack Algorithm

---

Link

12865번 : 평범한 배낭

W[i] = i번째 물건의 무게, V[i] = i번째 물건의 가치

dp[i][w] = i번째 물건까지 보고 무게를 w만큼 채웠을 때 가치의 최대값

여기서 우리는 현재 가방에 i번째 물건을 넣었을 때의 가치와 넣지 않았을 때의 가치를 비교해 볼 것임.

dp[i][w]= max(dp[i-1][w], dp[i-1][w-W[i]))

#include <iostream>
using namespace std;
int dp[101][100001];
int W[101];
int V[101];

int main()
{
    int N, K; cin >> N >> K;
    for(int i=1; i<=N; ++i) { cin >> W[i] >> V[i]; }

    for(int i=1; i<=N; ++i)
    {
        for(int w=0; w<W[i]; ++w)
        {
            dp[i][w] = dp[i-1][w];
        }
        for(int w=W[i]; w<=K; ++w)
        {
            dp[i][w] = max(dp[i-1][w], dp[i-1][w-W[i]] + V[i]);
        }
    }
    cout << dp[N][K] << '\n';
}

---