C++ SWEA 3282. 0/1 Knapsack

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWBJAVpqrzQDFAWr

SW Expert Academy

풀이

정말 중요하고 기본적인 동적계획법 알고리즘 문제 ... 작년에 0/1 냅색 문제를 접하고 많은 DP문제를 풀었지만 알고리즘 손 놓아버리니 dp기억이 안나서 참,,, 힘든 문제였습니다. 결국 유튭에서 dp관련 영상보고 혼자서 구현해보았다,, 

 

일단 이 문제에서 이차원 배열을 선언하고 = dp[i][j]

i는 몇 번째 물건까지 사용하는지 , ex) i=3 , 1~3번째 물건까지 사용하겠다.

j는 부피가 몇인지 

 

해서 각 배열의 값에는 최적의 값(가치)이 들어있다 !

 

조건은

1.  각 물건의 부피가 j보다 작다면 

 1) 물건을 넣지 않았을 경우

 2) 그 물건의 가치 + 그 물건의 부피를 빼줬을 때 (공간 확보)

 

2. 부피가 j보다 크다면 

 1) 물건을 못 넣을 경우 

 

이렇게 3가지로 나눠서 볼 수 있다.

 

---

#include <algorithm>
#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
 
int dp[101][1001]{ 0, }; //dp
int v[1001]; // 부피
int c[1001]; // 가치
int main() {
    int test_case= 0;
    cin >> test_case;
 
    for (int i = 0; i < test_case; i++) {
        int number, volume;
        cin >> number >> volume;
        for (int j = 1; j <=number; j++) {
            int tmp1,tmp2;
            cin >> tmp1 >> tmp2;
            v[j] = tmp1;
            c[j] = tmp2;
        }
 
        for (int k = 1; k <= number;k++) {
            for (int j = 1; j <= volume; j++) {
                if (v[k]<=j) { // j보다 무게가 작을 때
                    dp[k][j] = max( c[k] + dp[k - 1][j - v[k]], dp[k - 1][j]); 
                    // k번째 물건을 넣었을 경우와 넣지 않았을 때 경우 고려
                }
                else { // j보다 무게가 클 때는 그 전에 가장 큰 것으로
                    dp[k][j] = dp[k - 1][j];
                }
            }
        }
        cout<<"#"<<i+1<<" " << dp[number][volume] << endl;
        memset(dp, 0, sizeof(dp));
        memset(v, 0, sizeof(v));
        memset(c, 0, sizeof(c));
    }
 
 
    return 0;
}