백준 12865번, 평범한 배낭

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

12865번: 평범한 배낭

유명한 0/1 knapsack problem 다이나믹 프로그래밍 문제입니다.

 

사실 저도 못 풀어서 결국에는 검색을 통해 알게 된 문제...

 

 

https://gsmesie692.tistory.com/113

Dynamic Programming: 배낭 채우기 문제 (Knapsack Problem)

위 주소는 knapsack problem을 잘 정리되어있어 참고하는데 도움을 받았습니다.

 

 

dp[i][j]에서 i는 물건 i번째까지 가방에 넣은 것을 의미하고 j는 배낭에 담을수 있는 무게를 뜻합니다.

그러므로 물건을 담는 경우와 담지 않는 경우 2가지를 생각해야합니다. 

 

위 문제의 예제에서 첫번 째 물건(무게 6 가치 13)

첫 번째 물건만 담았을 때 최대 무게에 대한 최대 가치입니다.

 

두번 째 물건(무게 4 가치 8)

 

두 번째 물건만 담았을 때 최대 무게에 대한 최대 가치입니다. ( 두 번째 물건만입니다. 혼동하지마세요)

즉, j가 4나 5인 경우 가치가 8인 물건을 담을 수 있지만 j가 6이나 7인 경우 첫 번째 물건 13이 최대 가치입니다.

 

세 번째 물건은 무게가 3, 가치가 6입니다.

무게가 3이므로 i가 3이고 j가 3일때, 6의 최대 가치를 갖고

j가 4나 5인 경우 두 번째 물건의 무게가 4이므로 해당하는 가치가 들어갑니다.

j가 6이나 7인 경우에도 마찬가지로 첫 번째 물건의 가치가 가장 높기때문에 표시합니다.

하지만, 이렇게 하면 틀립니다.

여기서 j가 7인 경우에는 두 번째 물건의 무게가 4, 세 번째 물건의 무게가 3이므로 j가 7인 자리에는

각각의 가치를 더한 값인 14가 들어온다는 것이죠. 

즉 이것을 점화식으로 나타낸다면 dp[i][j] = max(dp[i][j], dp[i-1][j-w]+v)로 나타낼 수 있다는 것이죠.

네 번째 물건을 입력하게 되면 이런 식으로 표가 작성됩니다.

 

#include<iostream>
#include<algorithm>

using namespace std;

int main(){
    int N;
    int K;
    int W;
    int V;
    int dp[101][100001] ={0};
    int maxi = 0;
    cin>>N>>K;
    for(int i = 1; i <= N; i++){
        cin>>W>>V;
        for(int j = 1; j <= K; j++){
              dp[i][j] = max(dp[i][j], dp[i-1][j]);
              if(j>=W){
                dp[i][j] = max(dp[i][j], dp[i-1][j-W]+V);
                maxi = max(maxi, dp[i][j]);
            }
        }
    }
    cout<<maxi;

    return 0;
}