문제

DP 중 유명한 냅색 문제입니다.

---

풀이

1. 무게가 작은 순으로 넣어보기

가치 무게

• 1 1kg
• 2 2kg
• 2 3kg
• 3 4kg
• 10 10kg
  앞에 네개를 넣으면 1+2+3+4=8kg이고 가치는 8입니다.
  맨 마지막 하나만 넣으면 10kg이고 가치는 10입니다.
  무게가 작은 순으로 넣으면 안되는 것을 알 수 있습니다.

2. 가치가 큰 순으로 넣어보기

가치 무게

• 10 10kg
• 9 1kg
• 5 2kg
  위에서 부터 차례대로 넣다보면 가치가 10인 10kg짜리를 넣게 되는데 이는 가치가 9인 1kg을 여러개 넣는것이 가치가 더 커질 수 있으므로 가치가 큰 순으로 넣어보기도 안됩니다.

3. 모든 경우의 수를 따져보기

ABCD가 있을 경우
A가 있을경우 없을 경우, B가 있을 경우 없을 경우 총 2^N개의 경우의 수 를 따져봐야합니다.

---

코드

#include<iostream>
#include<cstring>
using namespace std;

int dp[101][1001]; // dp테이블 생성
int N, K;
int V[101], C[101]; // 부피배열 V와 가치 배열 C

int run(int idx, int v) {
	if (dp[idx][v] != 0)return dp[idx][v]; // 방문한 적 있으면 리턴
	if (idx == N) { return 0; } // 범위를 넘어가면 종료
	int a = 0, b = 0;
	if (V[idx] + v <= K) { // 넣을 때
		a = C[idx] + run(idx + 1, V[idx] + v);
	}
	b = run(idx + 1, v); // 안넣을 때
	dp[idx][v] = max(a, b); // 최댓값 기억하기

	return dp[idx][v]; // 최댓값 리턴
}

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

	cin >> T;

	for (test_case = 1; test_case <= T; ++test_case)
	{
		cin >> N >> K;
		for (int i = 0; i < N; i++) {
			cin >> V[i] >> C[i];
		}
		cout << "#" << test_case << " " << run(0, 0) << '\n';
		memset(dp, 0, sizeof(dp)); // dp테이블 초기화
	}
	return 0;//정상종료시 반드시 0을 리턴해야합니다.
}