12865호: 일반 백팩
첫 번째 줄은 항목 수 N(1≤N≤100)과 기준이 견딜 수 있는 가중치 K(1≤K≤100000)를 제공합니다.
두 번째 라인부터 N라인까지는 각 오브젝트의 가중치 W(1≤W≤100000)와 오브젝트 V의 값(0≤V≤1000)
www.acmicpc.net
트리 구조로 생각하십시오. 주어진 입력을 가정하고 첫 번째 로드에서 마지막 로드까지 순차적으로 반복합니다.
N번째 짐을 만났을 때 선택할 수 있는 시나리오는 두 가지다.
놓을 것인가 말 것인가.
즉, (가방 개수)*(무게)의 dp 배열이 있고, 이 배열에는 역기를 들 때 누릴 수 있는 최대 효용이 포함되어 있다면
1. 가방에 넣지 않는 경우
=> dp(i-1)(j)가 0이 아니면 그 값을 그대로 dp(i)(j)에 저장한다.
N번째 하중을 먼저 넣는 경우를 생각해서 dp(i)(weight(i))에 value(i)를 넣습니다.
2. 가방에 넣는 경우
=> dp(i-1)(j)가 0이 아닌 경우(= 이전에 짐을 실은 적이 있는 경우) j(==기존 무게)+무게(i)가 허용 무게 범위를 초과하는지 확인, 초과할 경우 아니면 dp(i)(j-1)+value(i)를 dp(i)(j+weight(i))에 넣습니다.
이와 같이 dp배열의 마지막 줄에는 모든 짐을 가방에 넣는 경우의 수와 각 무게에 따른 효용성을 저장하므로 최대값을 출력할 수 있다.
————————————————– ————————————————– ————————————————– —
내가 찾으려고 했던 것이 “최대 무게를 초과하지 않고 가방에 들어갈 수 있는 항목 조합의 최대 유용성”이었기 때문에 내가 이것을 했을 때 내가 틀렸습니다.
예를 들어 7kg을 같은 방법으로 넣어도 효용이 다를 수 있으니 그렇다면 dp 배열을 채울 때 효용이 더 작은 쪽을 고려할 필요가 없다.
따라서 1단계와 2단계에는 “최대한의 효용가치를 얻어 투입하는” 과정이 추가되어야 한다.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int N, K;
cin >> N >> K;
vector<int> weight(N + 1);
vector<int> value(N + 1);
for (int i = 1; i < N + 1; i++)
{
cin >> weight(i);
cin >> value(i);
}
vector<vector<int>> dp(N + 1, vector<int>(K + 1));
for (int i = 1; i < N + 1; i++)
{
for (int j = 1; j < K + 1; j++)
{
if (dp(i - 1)(j) !
= 0)
{
// 1. 이전까지 추가된 짐에 현재 짐 추가 2. 이전까지 추가된 짐만 두고 현재 짐은 추가 x
dp(i)(j) = max(dp(i)(j), dp(i - 1)(j));
if (j + weight(i) <= K)
{
dp(i)(j + weight(i)) = max(dp(i - 1)(j) + value(i), dp(i)(j + weight(i)));
}
}
}
// 3. 이번 짐만 처음으로 추가하는 경우
if (weight(i) <= K)
{
dp(i)(weight(i)) = max(value(i), dp(i)(weight(i)));
}
}
int ans = 0;
for (int i = K; i > 0; i--)
{
ans = max(ans, dp(N)(i));
}
cout << ans;
}