[DP] SWEA 3282 0/1 Knapsack C++

 

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

#include <iostream>
#include <cstring>

using namespace std;

int v[101], c[101];
int dp[101][1001];

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

	for(test_case = 1; test_case <= T; ++test_case) {
		int n, k;
		cin >> n >> k;
		for(int i=1; i<=n; i++) cin >> v[i] >> c[i];

		memset(dp, 0, sizeof(dp));
        
		// dp[i][j] = i번째 물건 사용, j만큼의 부피 사용 최대 가치(1부터 시작)
		for(int i=1; i<=n; i++) {
			for(int j=1; j<=k; j++) {
				if (j >= v[i]) dp[i][j] = max(dp[i-1][j], dp[i-1][j-v[i]]+c[i]);
				else dp[i][j] = dp[i-1][j];
			}
		}
		cout << "#" << test_case << " " << dp[n][k] << endl;
	}
	return 0;
}