[C++] 12865: 평범한 배낭

정답

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int N, K;
int W[100001] = { 0 };
int V[101] = { 0 };
int DP[101][100001];


int main() {

	cin >> N >> K;

	for (int i = 1; i <= N; i++) {
		cin >> W[i] >> V[i];
	}


	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= K; j++) {
			if (W[i] <= j) DP[i][j] = max(DP[i - 1][j], V[i] + DP[i - 1][j - W[i]]);
			else DP[i][j] = DP[i - 1][j];
		}
	}

	cout << DP[N][K];

}

DP[i][j]는, 물건을 i개 넣는 경우에서 무게가 j일 때 가치의 최대 값

1. i = 1, w = 6, v = 13

2. i = 2, w = 4, v = 8
   

3. i = 3, w = 3, v = 6
   

4. i = 4, w = 5, v = 12

최종적으로 답은 D[4][7] = 14가 된다.

오답

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
	int N, K, W, V;

	cin >> N >> K;

	vector<int>* v = new vector<int>[K + 1];
	int* DP = new int[K + 1];

	for (int i = 0; i < N; i++) {
		cin >> W >> V;
		v[W].push_back(V);
		DP[i] = max(DP[i], V);
	}

	for (int i = 0; i < N; i++) {
		if (v[W].size() > 1) {
			for (int j = 1; j <= v[W].size(); j++) {
				
			}
		}
	}

	int ans = 0;

	for (int i = 1; i < K + 1; i++) {
		if (i + (i - 1) <= K) {
			DP[i + (i - 1)] = max(DP[i + (i - 1)], DP[i] + DP[i - 1]);
		}
	}
	
	for (int i = 0; i < K + 1; i++) {
		if (DP[i] >= ans) ans = DP[i];
	}

	cout << ans;
}

DP[weight]에 value를 저장
같은 무게가 입력되면 value가 더 높은 값을 저장해주었다
그리고 f(2 * X - 1) = f(X-1) + f(X)의 점화식에 따라 DP에 값을 입력해서, DP 배열 안에서 가장 큰 값을 정답으로 출력
틀린 이유: 같은 무게가 입력됐을 때 value가 상대적으로 작은 값은 저장되지 않고 삭제되기 때문에 같은 무게의 물건을 배낭에 여러 개 넣는게 정답인 경우가 제외되었다 ㅠ_ㅠ