12865

백준 12865번

Link: 12865번: 평범한 배낭

---

문제 설명

Knapsack 문제가 조금 변형된 형태의 문제다.

사실 변형된 문제인지는 잘 모르겠다. 예전에 Knapsack 풀때 썼던 아이디어랑은 좀 다른것 같아서 변형됐다고 생각은 하고 있는중.

평범한 Knapsack 문제 푸는대로 풀면 물건을 여러번 써가면서 가방을 채우는게 돼서 틀린다.

물건을 한번만 쓰면서 가방을 채우는 방법에 대해 생각해봐야 하는 문제.

2차원 배열을 쓰는 DP로 풀어보려 했는데 헷갈리기도 하고 막상 풀어봤는데 틀려서 결국 답을 봤다.

DP배열의 각 인덱스는 가방의 무게를 의미한다고 생각하고 시작했다.

각 물건들에 대해 인덱스값이 더 크거나 같을 경우 DP[j]와 DP[j - items[j]의 무게] + items[j]의 가치를 비교해서 둘중 더 큰값으로 DP 배열을 채웠다.

답 보고 풀고 나니 이걸 왜 생각못했나 하는 생각이 많이 들었다.

별로 어려워보이는 알고리즘도 아니었고 내가 생각했던 알고리즘이랑 크게 다르지 않았는데 난 못풀었다는 생각에 자괴감이 들더라.

---

정답 코드

//
// Created by Keith_Lee on 24/03/2019.
//

#include <iostream>

using namespace std;

struct item{
    int W, V;
};

int N, K;

int DP[100001] = {0, };

int main(){
    cin >> N >> K;

    item items[101];

    for(int i=0; i<N; i++){
        int weight, value;
        cin >> weight >> value;

        items[i] = {weight, value};
    }

    for(int i=0; i<N; i++){
        for(int j=K; j>=0; j--){
            if(items[i].W <= j){
                DP[j] = max(DP[j], DP[j-items[i].W] + items[i].V);
            }
        }
    }

    cout << DP[K] << '\n';

    return 0;
}

---