[C++] 백준 12865번 평범한 배낭

다이나믹 프로그래밍 문제입니다.

무게 w의 배낭에 물건을 넣을 때 물건의 가치가
가장 높게 들어갔을 때의 값을 출력하는 문제입니다.

먼저 vector로 받아서 무게를 기준으로 정렬하였습니다.
작은 숫자부터 차례대로 DP배열에 넣었습니다.
DP배열 인덱스의 의미는 각 무게에 들어갈 수 있는 가치의 최대치를 넣습니다.
물품은 한 번만 넣을 수 있기에 뒤에서 부터 시작했습니다.

1. 무게 3일때의 최대치
2. 무게 3일때의 최대치 + 4일 때의 최대치
3. 무게 3일때의 최대치 + 4일 때의 최대치 + 5일 때의 최대치
4. 무게 3일때의 최대치 + 4일 때의 최대치 + 5일 때의 최대치 + 6일 때의 최대치

ex)

1. ----------------------
   0  1  2  3  4  5  6  7
3                          x

   0  1  2  3  4  5  6  7
3                x  x  x  x

   0  1  2  3  4  5  6  7
3            6  x  x   x  x
-------------------------

2. ----------------------
   0  1  2  3  4  5  6  7
3            6  x  x   x  x
4                         14

   0  1  2  3  4  5  6  7
3            6  x  x   x  x
4                   x   x 14

   0  1  2  3  4  5  6  7
3            6  x  x   x  x
4               8   x  x 14
-------------------------

3. ----------------------
   0  1  2  3  4  5  6  7
3            6  x   x  x  x
4            6  8   x  x 14
5                  12  x 14
-------------------------

4. ----------------------
   0  1  2  3  4  5  6  7
3            6  x   x  x  x
4            6  8   x  x 14
5                   12 x  14
6                      13 14
-------------------------

* 점화식

DP[j] = input[i][1] + DP[j - x];

i는 현재 확인중인 무게
j는 뒤에서부터 무게를 중심으로 가중치를 더하는 과정
input[x][0] = 0은 무게
input[x][1] = 1은 가중치
                  

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

int main(int argc, char *argv[])
{
	vector <vector<int>> input;
	int DP[100010];
	int temp[100010];
	int n;
	int w;
	int maxNum = -987654321;

	memset(DP, 0, sizeof(DP));
	memset(temp, 0, sizeof(temp));

	cin >> n;
	cin >> w;

	for (int i = 1; i <= n; ++i) {
		int weight, value;
		vector <int> v;

		cin >> weight;
		cin >> value;

		v.push_back(weight);
		v.push_back(value);

		input.push_back(v);
	}

	sort(input.begin(), input.end());

	for (int i = 0; i < n; ++i) {
		int x = input[i][0];
		for (int j = w; j >= x ; --j) {
			if (DP[j] < input[i][1] + DP[j - x] && (j - x == 0 || DP[j - x] != 0)) {
				DP[j] = input[i][1] + DP[j - x];
			}
		}
	}

	for (int i = 1; i <= w; ++i) {
		maxNum = max(maxNum, DP[i]);
	}

	cout << maxNum << endl;

	return 0;
}