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

swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWBJAVpqrzQDFAWr&categoryId=AWBJAVpqrzQDFAWr&categoryType=CODE

SW Expert Academy

 

DP의 대표적인 알고리즘 문제.

N개의 물건 중에서 최대 W만큼의 무게를 가방에 넣을 때 구할 수 있는 최댓값을 구하면 된다.

 

이 문제를 푸는데 매우 중요한 개념이 아래 블로그에 나와있다.

참고하여 코드를 보면 이해를 할 수 있다..!

gsmesie692.tistory.com/113

Dynamic Programming: 배낭 채우기 문제 (Knapsack Problem)

 

#include <iostream>
#include <vector>

using namespace std;

int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    int t;
    cin >> t;
    
    for(int tc = 1; tc <= t; tc++)
    {
        int v[101][1001];
        int w[101];
        int c[101];
        int N, W, answer = 0;
        cin >> N >> W;
        
        for(int i = 1; i <= N; i++)
            cin >> w[i] >> c[i];
        
        for(int i = 1; i <= N; i++)
        {
            for(int j = 1; j <= W; j++)
            {
                if(w[i] > j)
                    v[i][j] = v[i - 1][j];
                else
                    v[i][j] = c[i] + v[i - 1][j - w[i]] > v[i - 1][j] ? c[i] + v[i - 1][j - w[i]] : v[i - 1][j];
            }
        }
        cout << "#" << tc << " " << v[N][W] << endl;
    }
    return 0;
}