최고 17kg의 무게를 저장할 수 있는 가방이 있다. 그리고 각각 3kg, 4kg, 7kg, 8kg, 9kg의

무게를 가진 5종류의 보석이 있다. 이 보석들의 가치는 각각 4, 5, 10, 11, 13이다.

이 보석을 가방에 담는데 17kg를 넘지 않으면서 최대의 가치가 되도록 하려면 어떻게 담아야

할까요? 각 종류별 보석의 개수는 무한이 많다. 한 종류의 보석을 여러 번 가방에 담을 수 있

다는 뜻입니다.

첫 번째 줄은 보석 종류의 개수와 가방에 담을 수 있는 무게의 한계값이 주어진다.

두 번째 줄부터 각 보석의 무게와 가치가 주어진다.

가방의 저장무게는 1000kg을 넘지 않는다. 보석의 개수는 30개 이내이다.

첫 번째 줄에 가방에 담을 수 있는 보석의 최대가치를 출력한다.

4 11\

5 12\

3 8\

6 14\

4 8

28

해설: 5g 1개, 3g 2개를 선택해서 28가치가 최대이다.

``` Cpp

#include <iostream>

#include <fstream>

#include <vector>

#include <algorithm>

using namespace std;

int main() {

ios_base::sync_with_stdio(false);

ifstream cin;

cin.open("input.txt");

int n = 0, m = 0, w = 0, v = 0;

cin >> n >> m;

vector<int> dy(m + 1, 0);

for (int i = 0; i < n; i++) {

cin >> w >> v;

for (int j = w; j <= m; j++) {

// 현재 가방의 최대 가치

// vs

// 현재 w라는 무게를 뺀 현재 가방의 공간에 담을 수 있는 최대 가치 + 현재 보석의 무게

// 현재 가방의 최대 가치와 새로운 보석을 넣었을 경우 최대 가치를 비교해서 더 큰값을 dy에 반영한다.

dy[j] = max(dy[j], dy[j - w] + v);

// d[j-w]에서 j-w를 한 이유

// w라는 무게를 갖는 보석을 가방에 담겠다고 가정했을 때문에 j-w를 함

// 그만큼의 무게를 빼줘야 가방의 현재 여유 공간이 얼마인지 알 수 있기 때문에

// 따라서 d[j-w]의 의미는 현재 w라는 무게를 뺀 현재 가방의 공간에 담을 수 있는 최대 가치이다.

}

}

cout << dy[m];

return 0;

}