[백준/C++] 12856번: 평범한 배낭

https://www.acmicpc.net/problem/12865

12865번: 평범한 배낭

• 코드

#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <stdio.h>
#include <queue>
#include <vector>
#include <unordered_map>
#include <set>
#include <map>
#include<cmath>
#define LL long long
using namespace std;
int dp[100][100001];
int main() {
	
	memset(dp, 0, sizeof(dp));
	int n = 0;
	int k = 0;
	int w[100];
	int v[100];
	cin >> n >> k;
	for (int i = 0; i < n; i++) {
		cin >> w[i] >> v[i];
	}
	for (int i = 1; i < k + 1; i++) {
		for (int j = 0; j < n ; j++) {
			if (w[j] <= i && j==0) {
				dp[j][i] = v[j];
			}
			else if (w[j] <= i && j != 0) {
				dp[j][i] = max(v[j] + dp[j - 1][i - w[j]], dp[j-1][i]);
			}
			else if (w[j] > i && j==0) {
				dp[j][i] = 0;
			}
			else if (w[j] > i && j != 0) {
				dp[j][i] = dp[j - 1][i];
			}
			
		}
	}
	cout << dp[n - 1][k] << endl;
	return 0;
}

• 알고리즘 분류 : 다이나믹 프로그래밍
• 문제해설

나는 dp에 소질있다고 생각했던 것을 후회하게했던 문제였다... 결국 구글링의 도움을 받으며 해결했는데 

유명한 문제라고 하니 알고리즘을 기억해두는게 좋을 것 같다.

최대 무게를 1부터 늘려가는 것까진 생각했었다. 최대무게가 1일 때 가장 큰 가치합을 갱신하고 2일때는 1일 때에 최대무게가 1인 가치합을 더 더해야 하나? 그런데 무게가 2일때의 가치합도 고려해야하니 있으니 숫자가 더 커지게 되면 점점 경우의 수가 커질텐데..? 라는 생각에서 멈췄었다.

정답은 물건의 무게나 가치 숫자를 기준으로 굳이 정렬하거나 무게가 몇일 때가 있는지를 찾지 않고 입력받은 순서대로 생각해나가는 것이었다. (이미 최대 무게를 기준으로 잡았으니)

 

https://nanyoungkim.tistory.com/182

[C++] 백준 12865번 - 평범한 배낭 (자세한 설명, DP, Knapsadck Problem)

결국 이 블로그를 참고했다.

최대 가치합을 한 변수에만 담아서 계속 갱신하는게 아니라 2차원 dp배열을 통해 저장해나가는게 포인트인 것 같다. 저번에도 이런식으로 하지 않아서 틀렸던 것 같은데 왜 계속 같은 실수를 반복할까....ㅜ

dp[최대무게][물건개수]로 공간을 만든다.

최대무게 1부터 물건들을 차례로 담을 수 있는지 본다.

물건의 무게가 최대무게보다 크면 그 물건은 그 최대무게의 상황에서 당연히 담을 수 없다. 따라서 이전 물건까지의 가치합이 여전히 최대 가치합이므로 이전 물건까지의 최대 가치합을 저장해준다. 이렇게 해야하는 이유는 나중에 물건을 담고도 최대 무게보다 작아서 나머지 무게만큼 더 담아봐야하는 상황이 생길 때 바로 이전물건에 최대 가치합이 있어야 접근하기 쉽기 때문이다. 그렇지 않으면 또 처음부터 이전 물건까지 반복문을 돌려줘야할 것이다. 

그리고 또 한가지 헷갈렸던 점인데 최대 무게에 들어간다고 물건의 가치합을 이전과 바로 합해주면 안된다. 반드시 현재 물건의 무게와 나머지 무게는 이전에 구한 최대무게일 때의 이전 물건까지의 최대 가치를 더해준 값을 저장하거나 이전 최대 가치만 저장해야지 dp의 규칙이 꼬이지 않는다. 깊이 생각해보면 맞는 얘기인데 코드를 짜다보면 자꾸 이전 가치를 바로 누적하고 싶은 생각이 든다...ㅋㅋ

최대무게를 초과했는데 첫번째 물건이라면 전 무게일 때도 반드시 초과했을 것이기 때문에 가치 0을 저장하고,

최대무게를 초과하지 않았지만 첫번째 물건이라면 이것보다 더 큰 가치합은 없었을 것이기 때문에 첫번쨰 물건의 가치를 저장한다.

끝.