Knapsackアルゴリズム(標準12865-普通リュック)

リュックサックの問題と呼ばれるタイプもあります.
その問題とこの問題を解くアルゴリズムを理解してみましょう.
質問する
質問元:白準12865号-普通リュック
この問題は普通のリュックサックについての問題です.
一ヶ月後に国から召喚されたジュンヒは旅行に行く.悲しい世との隔絶、最大限楽しむ旅なので、持ち歩くリュックもできるだけ安くなります.
旅行が必要だと思っているものがN点ある.どれも重量Wと価値Vがあり、リュックサックに入れると準本でVを楽しむことができます.まだ行軍したことのない俊書は最大Kのリュックサックしか持っていない.できるだけ楽しく旅行するために、リュックサックに入れられるものの価値の最低価格を教えてあげます.
アイデア
この問題をどうするか考えさせてください.
まず、すべてのものに対して、私たちは2つの選択があります.装わない.
しかし、この選択が最後に判断しなければならない問題であり、最も重要なのは何だろうか.
最後に選んだものとリュックサックに残った容量.
では、局所的な問題をすることができます.Pack(capacity, itemnumber):キャリア上の容量が十分に大きい場合、itemnumber後の物品を梱包した後に得られる価値の最低価格.
そしてさっき思ったものを詰めるか、入れないかの2つに分けます.
(weight[i], value[i]:i最初のものの重さと価値)

未マウント:Pack(capacity,itemnumber + 1)

含まれる場合(この場合、capacity >= weight[item]は当然):Pack(capacity - weight[item], itemnumber + 1) + value[item]品物が入っているので、残容量から品物の重量を差し引くと、pack関数は価値を返しますので、品物の価値を増やします.

そのため、どちらの場合も、最高値を戻せばよい.
プールコード
他のコードではなくpack(int w, int number)関数を参照してください.

#include <iostream>
#include <algorithm>
#include <string.h>
using namespace std;
int n,k;    // n : 물품의 수, k : 버틸 수 있는 무게.
int item[100];
int weight[100];
int value[100001][100];

int pack(int w, int number){
    if (number == n)  // 더 담을 물건이 없넹? 물건 번호가 0부터 n-1까지니까.
        return 0;
    int &ret = value[w][number];
    if(ret != - 1)
        return ret;

    ret = pack(w,number+1);     // 담지 않는 경우.
    if(w >= weight[number])	// 물건이 배낭에 들어갈 수 있을 때 담아야 한다.
        ret = max(ret, pack(w-weight[number], number+1) + item[number]);	// 담지 않는 경우와 담는 경우 중 큰 값은?

    return ret;

}
int main(){
    cin >> n >> k;
    int w,v;
    memset(value,-1,sizeof(value));
    for(int i = 0; i < n; i++){
        cin >> w >> v;
        weight[i] = w;
        item[i] = v;
    }

    pack(k,0);
    cout << value[k][0];
    return 0;
}

これはLISアルゴリズムよりずっと簡単なようだ.