Algorithm) SWEA 3282 0 / 1 knapsack

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

SW Expert Academy

유명한 문제죠? 

처음에 딱 보고 바로 백트래킹이 떠올랐지만 최대 입력이 1000개이기에 dp를 썼습니다!

#include<iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;


int main(int argc, char** argv)
{
    int test_case;
    int T;
    cin>>T;

    for(test_case = 1; test_case <= T; ++test_case)
    {
        int arr[102][102] = {0};
        int dp[102][1002] = {0};
        int n,k;
        int ans = 0;
        cin >> n >> k;
        for(int i=1; i<=n; i++) {
            int v,c;
            cin>>v>>c;
            arr[i][0] = v;
            arr[i][1] = c;
        }

        for(int i=1; i<=n; i++) {
            for(int j=1; j<=k; j++){
                int weight = arr[i][0];
                int value = arr[i][1];

                if(j < weight) {
                    dp[i][j] = dp[i-1][j];
                } else {
                    dp[i][j] = max(dp[i-1][j], dp[i-1][j-weight] + value);
                }
            }
        }
        cout<<"#"<<test_case<<" "<<dp[n][k]<<"\n";
    }
    return 0;
}