ダイナミックプランニング0-1リュック問題

1263 ワード

問題の説明:
N種類の品物とリュックサックを1つ与えます.アイテムiの重量はWiで、その価値ビットVi、リュックサックの容量はCです.リュックサックに入るものをどのように選んで、リュックサックに入るものの総価値を最大にするべきですか?
物品を選択する際、各物品iには、リュックサックに入れるか、リュックサックに入れないかの2つの選択しかない.物iを複数回入れたり、物の一部だけ入れたりすることはできません.そのため、この問題は0-1リュックサック問題と呼ばれている. 
 
問題解析:V(i,j)を前i(1<=i<=n)個の物品にj(1<=j<=C)のリュックサックに入れることができる物品の最大価値を示すと,次のような動的計画関数が得られる.
(1)   V(i,0)=V(0,j)=0 
(2)V(i,j)=V(i-1,j)ji第iの物品の重量がリュックサックの容量より大きい場合、人の前iの物品を詰める最大価値と、前i-1の物品を入れる最大価格は同じであり、すなわち物品iがリュックサックに入れられない
V(i,j)=max{V(i-1,j),V(i-1,j-wi)+vi)}j>wi i番目の物品の重量がリュックサックの容量よりも小さい場合、(a)i番目の物品をリュックサックに入れると、リュックサック物品の価値はi-1番目の物品が容量位j-wiのリュックサックに入れる価値にi番目の物品の価値viを加える.(b)i番目の物品がリュックサックに入れられていない場合、リュックサックにおける物品価値は、前のi−1個の物品を容量jのリュックサックに入れて得られた価値に等しい.明らかに,両者の中で最も価値のあるのは,前のi個の物品を容量jのリュックサックに入れる最適解である.
コード:
#include 

using namespace std;
int findMaxValue(int weight[],int value[],int n,int m){
    int res;
    int a[n+1][m+1];
    for(int i=0;i>n>>m;
    int weight[n];
    int value[n];
    for(int i=0;i>weight[i]>>value[i];
    cout<