백준[baekjoon] 12865

#include<cstdio>
#include<algorithm>
#include<vector>

using namespace std;

const int MAX_N = 100 + 5;
const int MAX_W = 100100;


int main()
{
	int N, K;
	int W[100100];
	int dp[MAX_N][MAX_W]; // dp[i][j] = [0...i]번 배낭을 사용하여 총합무게 j일때 얻을 수 있는 가치의 최댓값
	
	int weight[MAX_N], value[MAX_N];
	scanf("%d %d", &N, &K);

	for (int i = 1; i <= N; i++)          // [1...N]
		scanf("%d %d", &weight[i], &value[i]);

	for (int i = 0; i <= N; i++) {        // i-th item
		for (int j = 0; j <= K; j++) {    // j : total weight
			
			if (j == 0 || i==0) { 
				dp[i][j] = 0;
				continue;
			}

			if (j < weight[i])
				dp[i][j] = dp[i - 1][j];

			if (j - weight[i] >= 0)
				dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
		}
	}
	printf("%d", dp[N][K]);   // [0...N]번 배낭을 사용하여 총합무게K 일때 얻을 수 있는 가치의 최대값
	return 0;
}