[アルゴリズム解析]BOJ 12865普通リュックサック

今日の質問はBOJ 12865普通リュックです!
ゴールド5だからじゃなくて迫力ある挑戦でしたがこんなに難しくて自信があります楽しい.😞
DPの一種?Knapsackというアルゴリズムは初めて聞いたアルゴリズムですが、
それもDPの概念で解けるとは知らなかったけど、とにかく、DPももっと解けるように、やっぱり

BOJ 12865普通リュック

この問題は普通のリュックサックについての問題です.
一ヶ月後に国から召喚されたジュンヒは旅行に行く.悲しい世との隔絶、最大限楽しむ旅なので、持ち歩くリュックもできるだけ安くなります.
旅行が必要だと思っているものがN点ある.どれも重量Wと価値Vがあり、リュックサックに入れると準本でVを楽しむことができます.まだ行軍したことのない俊書は最大Kのリュックサックしか持っていない.できるだけ楽しく旅行するために、リュックサックに入れられるものの価値の最低価格を教えてあげます.

にゅうしゅつりょく

に答える

この問題の接近概念は2日前に解いたBOJ 9084コインの問題に似ています!
この問題にも2次元dp配列が必要である.
dp[i][j]には、最大j重量を充填しようとしたときに、0個の物品からi個の物品に使用される物品の最大価値の和がリストされている.

アイテム1:<6,13>

まず重さ6、価値3のものを使います.

重さ6のものは5以下で一番重いリュックサックを入れることはできません.したがって、重量vの物品であれば、物品を使用する前に、リュックサックの最大重量がvより小さい場合には、vを添加しないときの最大値を維持し、dp値は変わらず、これはいかなる物品を添加しないときの値0を維持する.

リュックの最大重量は6時です
物を置くには1、既存のバッグの重さは0です.
重さ0のリュックサックの価値は0で、品物1の価値は13で、dp[1][6] = 13と書かれています.

リュックの最大重量が7の場合
物品1を入れるには、既存のリュックサックの重量が1でなければならず、物品1を入れず、リュックサックの重量が1である場合、リュックサックの最大価値はdp[0][1] = 0であり、dp[1][7] = dp[0][1] + 13である.

アイテム2:<4,8>

こうしてdp[1]行を完成させ、今回は重量4、価値8のアイテム2を入れる.

リュックの最大重量は4時です
物2を入れて包みを完成させるには、物2を入れていない包みの重さは0でなければなりません!
このとき、dp[2][4] = dp[1][0] + 8 = 8となり、これまで物を置かなかった2よりも大きく、包み重さが4のときの最大値dp[1][4] = 0となったため、dp[2][4]のうち8となった.

リュックの最大重量は6時です
荷物2を入れてリュックサックを完成させ、荷物2を入れていないバッグの重さは2でなければなりません.この値はdp[1][2]に書かれています.
物2を入れると、バッグの価値はdp[1][2] + 8 = 8です.
物2を置かなければ、バッグの価値はdp[1][6] = 13なので、より大きな値を採用し、dp[1][6]の価格は13です.

このようにdp配列が完了し、すべてのアイテムが使用候補となり、最大重量Kのリュックの最大値dp[アイテム数][K]が正解に戻ります!

コード#コード#

#include <iostream>
#include <vector>

// BOJ 12865 평범한 배낭, DP
using namespace std;


int getMaxValue(vector<pair<int, int>> items, int K){
    vector<vector<int>> dp(items.size(), vector<int>(K+1));

    for (int i = 0; i <= K ; ++i) {
        dp[0][i] = 0;
    }

    for (int i = 1; i < items.size(); ++i) {
        // 배낭 전체 무게가 해당 아이템보다 작을 때는 기존의 dp 값 유지
        for (int j = 0; j < items[i].first; ++j) { 
            dp[i][j] = dp[i-1][j];
        }

        // i번째 아이템을 사용할 때와 사용하지 않았을 때 가치의 최댓값으로 dp 완성
        for (int j = items[i].first; j <= K ; ++j) {  
            int left = j - items[i].first;
            dp[i][j] = max(dp[i-1][j], dp[i-1][left] + items[i].second);
        }
    }

    return dp[items.size()-1][K];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int N, K;
    cin>>N>>K;
    vector<pair<int, int>> items(N+1, make_pair(0,0));

    for (int i = 1; i <= N; ++i) {
        cin>>items[i].first;
        cin>>items[i].second;
    }

    int value = getMaxValue(items, K);

    cout<<value;

    return 0;
}