SWEA 3282. 0/1 Knapsack (C++)

#include <iostream>
using namespace std;

int N, K;
int V[101], C[101];
int bag[101][1001];
int main()
{
    int tc = 0;
    cin >> tc;
    for (int t = 1; t <= tc; t++)
    {
        cin >> N >> K;

        for (int i = 1; i <= N; i++)
        {
            cin >> V[i] >> C[i];
        }

        for (int i = 1; i <= N; i++)
        {
            for (int j = 1; j <= K; j++)
            {
                if (V[i] > j)
                    bag[i][j] = bag[i - 1][j];
                else
                    bag[i][j] = max(bag[i - 1][j], bag[i - 1][j - V[i]] + C[i]);
            }
        }
        cout << "#" << t << " " << bag[N][K] << "\n";
    }
    return 0;
}

냅색 문제

1. 가방에 안넣기

  ▶  안넣는 기준: 현재 부피(j)와 현재 물건의 부피(bag[i]의 V[i]) 비교

                          현재 부피가 현재 물건의 부피보다 작다면 애초에 가방에 넣을수없다.

2. 가방에 넣기

   ▶ 전 물건의 현재 부피(bag[i - 1][j])의 가치와 현재 물건을 넣었을 때의 가치(bag[i - 1][j - V[i]] + C[i])와 비교

   ▶ bag[i - 1][j - V[i]] → 전 물건의 부피에서 현재 물건의 부피를 뺀 후의 가치

                                  → 현재 물건을 넣기위해서는 현재 물건의 부피를 빼줘야함