12865 - 평범한 배낭

첫번째 풀이

모든 경우의 수를 보려고 재귀를 이용하여 구현하였지만 시간초과!
N의 범위가 최대 100이기 때문에 2^100까지 가면 시간이 많이 걸린다.

#include <iostream>
using namespace std;

int N, K;
int W[101];
int V[101];

int knapsack(int w, int idx) {
	if (idx == N) { return 0; }
	int a = 0;
	if (w + W[idx] <= K) {
		//들어간 경우
		a =V[idx]+ knapsack(w + W[idx], idx + 1);
	}
	// 안들어간 경우
	int b=knapsack(w, idx + 1);
	return max(a, b);
}

int main() {
	cin >> N >> K;
	for (int i = 0; i < N; i++) {
		cin >> W[i] >> V[i];
	}
	
	cout << knapsack(0, 0);


	return 0;
}

시간을 줄일 수 있는 방법은 dp 테이블을 이용하는 것이다
dp[idx][무게]일때의 최대 가치 테이블에 계산한 값을 저장해주고 같은 값을 호출할 때 또 계산하는 것이 아닌 저장된 값을 return 해줌으로써 시간을 단축할 수 있습니다.

수정된 풀이

#include <iostream>
using namespace std;

int N, K;
int W[101];
int V[101];
int dp[101][100001];

int knapsack(int w, int idx) {
	// 시간 단축
	if (dp[idx][w] > 0) { return dp[idx][w]; }

	//종료 조건
	if (idx == N) { return 0; }
	int a = 0;
	if (w + W[idx] <= K) {
		//들어간 경우
		a =V[idx]+ knapsack(w + W[idx], idx + 1);
	}
	// 안들어간 경우
	int b=knapsack(w, idx + 1);

	// dp테이블의 최대가치를 저장후 max값 리턴
	return dp[idx][w]=max(a, b);
}

int main() {
	cin >> N >> K;
	for (int i = 0; i < N; i++) {
		cin >> W[i] >> V[i];
	}
	
	cout << knapsack(0, 0);


	return 0;
}