https://www.acmicpc.net/problem/12865
문제
> 이 문제는 아주 평범한 배낭에 관한 문제이다.
> 한 달 후면 국가의 부름을 받게 되는 준서는 여행을 가려고 한다.
> 세상과의 단절을 슬퍼하며 최대한 즐기기 위한 여행이기 때문에,
가지고 다닐 배낭 또한 최대한 가치 있게 싸려고 한다.
> 준서가 여행에 필요하다고 생각하는 N개의 물건이 있다.
> 각 물건은 무게 W와 가치 V를 가지는데, 해당 물건을 배낭에 넣어서 가면 준서가 V만큼 즐길 수 있다.
> 아직 행군을 해본 적이 없는 준서는 최대 K만큼의 무게만을 넣을 수 있는 배낭만 들고 다닐 수 있다.
> 준서가 최대한 즐거운 여행을 하기 위해 배낭에 넣을 수 있는 물건들의 가치의 최댓값을 알려주자.접근
dp를 사용해서 물건을 입력받을 때마다 그 물건으로 조합 할 수 있는 모든 dp값을 다 갱신해준다.
예를 들어 예제의 6,13이 들어오면
먼저 목표무게인 K=7를 만들기 위해
dp(7)과 dp(7-6)+13중에서 큰거를 고른다.
즉 지금 까지 무게 7중 가장 가치가 높았던 dp(7)과 방금 들어온 6짜리로 만들 수 있는 dp(1)+13중 뭐가 더 큰지 고르는것이다.
그리고 다음 들어올 물건들을 위해 dp(6)에 대해서도 최선의 수를 구해놓는다.
dp(6)과 dp(0)+13중 더 큰걸로 dp(6)을 기록해놓는다.
다음으로 4, 8짜리가 들어온다.
그러면 dp(7)부터 dp(4)까지 또 따져준다.
앞서 갱신했던 dp(7)과 dp(7-4)인 dp(3)+8 중 더 큰 걸 고른다.
그리고 dp(6)과 dp(2)+8 중 고르고, dp(5)와 dp(1)+8중에서 고르며 dp(4)와 dp(0)+8중에서 골라 각각의 최선들을 갱신해준다.
다음으로 3, 6이 들어온다. 또 7부터 3까지 따져준다.
dp(7)과 dp(4)+6중 고른다. 여기서 이제 앞에서 왜 반복문으로 들어온 무게까지 dp를 갱신했는지의 이유가 나온다.
앞서 dp(4)에 대한 최선의값을 구해 놨기 때문에 여기서 4와 3으로 만들 수 있는 최선의 dp(7)값이 나온다.
마지막으로 5,12에대해서도 똑같이한다.
그러면 최종적으로 각각 들어온 6,4,3,5에 대해
6은 0+6, 2+4, 3+3, 1+5
4는 0+4, 1+3
3은 0+3
5는 0+5, 1+4, 2+3
의 연산들이 이루어지고 이를 통해 각각의 최선의 경우들이 저장되어있다. 그럼 최종적으로 dp(7)은
1+6, 3+4, 4+3, 2+5의 연산이 행해졌고 이 중 max로 최댓값을 이미 선별한 상태이다.
따라서 dp(7)을 출력하면 그게 최대 값이다.
문제해결
> 물건 수, 목표 무게를 입력받고 최선의 경우를 저장할 벡터 dp를 무게가 0인 물건을 없으니 1부터 선언해준다.
> 물건 수 만큼 입력받으며 각 물건의 무게로 조합 할 수있는 목표 무게에 대한 경우를 전부 갱신해준다.
dp의 초기값을 전부 0으로 줬기 때문에 없는 물건 예를들어 dp2+ 5짜리무게 이런거는 0+5의 가치로 갱신된다.
> 마지막 물건 까지 다 보고 나면 가능한 경우를 다 따졌고 최대값 연산 까지 다 했기 때문에 dp(원하는 무게)해서 출력하면 된다.코드
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int N, K, W, V; // N = 물건 수, K = 최대 중량, W = 물건 중량, V = 가치
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> N >> K;
vector<int> dp(K + 1, 0);
while (N--)
{
cin >> W >> V;
for (int i = K; i >= W; i--)
{
dp[i] = max(dp[i], dp[i - W] + V);
}
}
cout << dp[K] << '\n';
}
후기
예제입력을 기준으로 잡고 가능한 모든 경우의 수를나열해 봤다.
1은 1
2는 2, 1+1
3은 3, 2+1, 1+1+1
4는 4, 3+1, 2+2, 2+1+1, 1+1+1+1
등등 특정 무게의 물건이 무조건 한개 씩만 있다는 조건이 없으므로 여러개일 때 까지 상정해서 이렇게 따졌다.
근데 이렇게 하면 여기서 만약 1짜리가 여러개라고 해도 2개 뿐이면 예를들어 4의 경우에서 1+1+1+1은 못만드니까 이런 예외는 어떻게 처리하지? 부터 시작해서
그럼 보통 dp는 전 단계들의 작은 dp들을 이용해 큰 dp를 구하는데 이렇게 각각 dp단계가 여러개면
예를들어 2일때 2짜리가 8이고 1짜리가 5,4,3라서 2를 선택했는데 3에선 2+1이 13이고 1+1+1이 12니까 이런 또 교차되는 부분은 어떻게하지? 같은 문제들이 생겼다.
예외를 위해 모든 반례와 경우를 따지려고 너무 멀리 본것 같다. 당장의 입력으로 들어온 애들로 가능한 조합만 따져주다보면 같은 무게의 물건이 여러개 들어와도 그때마다 가치가 다르니까 1짜리가 가치가 4, 6있으면 각각 dp(6)+4, dp(6)+6이렇게 알아서 따져지는것이다.
dp가 참어렵다.
