3282. 0/1 Knapsack

링크

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

SW Expert Academy

 

분류

동적 계획법(DP)

 

개인적 난이도

 

매우 쉬움

쉬움

보통

어려움

매우 어려움

 

핵심 알고리즘

동적 계획법을 이용하면 되는 너무나도 유명한 문제이다.

더불어, 백준 12865번과 동일한 문제이다.

https://www.acmicpc.net/problem/12865

12865번: 평범한 배낭

 

시행착오

없음

 

코드

#include<iostream>

using namespace std;

int cache[101][1001];

int xxx(int a, int b){
	return a > b ? a : b;
}

int v(int x, int y){
	if (x < -1 || y < 0) return -2100000000;
	if (x == -1) return 0;

	return cache[x][y];
}

int main(int argc, char** argv){
    int tc, T;
    scanf("%d", &T);

    for (tc = 1; tc <= T; ++tc)
    {
		int N, V;
		scanf("%d %d", &N, &V);

		for (int i = 0; i < N; i++){
			int vi, ci;
			scanf("%d %d", &vi, &ci);

			for (int j = 1; j <= V; j++){
				cache[i][j] = xxx(v(i - 1, j), v(i - 1, j - vi) + ci);
			}
		}

		printf("#%d %d\n", tc, cache[N - 1][V]);
    }

    return 0;
}