백준[baekjoon] 14728

전형적인 knapsack problem 문제이다.

#include<cstdio>
#include<algorithm>
#include<vector>
#include<string.h>

using namespace std;

typedef pair<int, int> pii;

const int MAX_N = 100;
const int MAX_T = 10010;

int cache[MAX_N][MAX_T];
int n, t;
pii test[MAX_N]; //{studyTime, score}

int solve(int idx, int time) // idx단원 이후에 얻을수있는 최대점수
{
	if (idx == n) return 0;
	
	int& ret = cache[idx][time];
	if (ret != -1) return ret;

	ret = solve(idx + 1, time); // idx단원 공부를 안 할경우
	
	if (time >= test[idx].first)
		ret = max(ret, solve(idx + 1, time - test[idx].first) + test[idx].second);
	return ret;
}

int main()
{
	memset(cache, -1, sizeof(cache));

	scanf("%d %d", &n, &t);
	for (int i = 0; i < n; i++) {
		scanf("%d %d", &test[i].first, &test[i].second);
	}
	printf("%d\n", solve(0, t));
	return 0;
}

 

#include<cstdio>
#include<algorithm>
#include<vector>
#include<string.h>

using namespace std;

typedef pair<int, int> pii;

const int MAX_N = 101;
const int MAX_T = 10010;

int dp[MAX_N][MAX_T]; // dp[idx][time] = [1..idx]단원중 선택하여 time이하의 시간으로 얻을 수 있는 최대점수
int n, t;
pii test[MAX_N]; //{studyTime, score}


int main()
{
	
	scanf("%d %d", &n, &t);
	for (int i = 1; i <= n; i++) {
		scanf("%d %d", &test[i].first, &test[i].second);
	}

	for (int i = 1; i <= n; i++) {
		for (int j = 0; j <= t; j++) {
			if (j < test[i].first) 
				dp[i][j] = dp[i - 1][j];
			else 
				dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - test[i].first] + test[i].second);
		}
	}
	printf("%d", dp[n][t]);
	return 0;
}