バックパック問題(01バックパック完全バックパック多重バックパック)

今日は牛客網のテーマを使って、リュックサックの問題の解を使います.ここでリュックの問題をまとめてみます.
リュックサックの問題は主に以下の3種類に分けられます.

01リュック

完全リュック

多重リュック

01リュックサックの問題
N個の品物とV容量のリュックサックがあります.i番目の品物の価格(すなわち体積、以下同)はw[i]、価値はc[i]である.どの品物をリュックサックに入れると、これらの品物の費用の合計がリュックサックの容量を超えず、価値の合計が最大になるかを解く.
これは私たちが最もよく出会うリュックサックの問題で、実は状態移動方程式を明らかにすればいいだけです.

f[i][v] = max(f[i-1][v], f[i-1][v-w[i]]+c[i])

この方程式を説明します.

の場合一:i番目は入れないが、この場合得られる価値は:f[i-1][v]

である.

ケース2:i番目を入れると、f[i-1][v-c[i]+w[i]

が得られます.
例を挙げて理解を深めましょう.ブルーブリッジカップの練習中の採薬問題です.
辰辰は天資聡明な子供で、彼の夢は世界で最も偉大な医者になることです.そのため、彼は近くで最も威信のある医者を師にしたいと思っています.医者は彼の資質を判断するために,彼に難題を出した.医者は彼を薬草だらけの洞窟に連れて行って言った.「子供、この洞窟にはいくつかの異なる薬草があります.それぞれの株を採るには時間がかかります.それぞれの株にも価値があります.私はあなたにしばらくの時間をあげます.この時間の中で、あなたはいくつかの薬草を採ることができます.もしあなたが賢い子供であれば、採った薬草の総価値を最大にすることができます.」もしあなたが辰辰だったら、あなたはこの任務を完成することができますか?入力記述Input Description入力1行目には2つの整数T(1<=T<=1000)とM(1<=M<=100)があり、1つのスペースで区切られており、Tは合計で採薬できる時間を表し、Mは洞窟内の薬草の数を表す.次のM行は各行に1~100の2つを含む(1と100を含む)の整数は、ある薬草を採取する時間とその薬草の価値をそれぞれ表す.出力記述Output Description出力は、所定の時間内に採取可能な薬草の最大総価値を示す1行のみを含む.Sample Input 70 3 71 100 69 1 2サンプルはSample Output 3データ範囲と提示Data Siを出力するze&Hint【データ規模】30%のデータに対して、M<=10;すべてのデータに対して、M<=100.

#include  
using namespace std; 
int dp[101][1001]; 
int main() 
{    
int t, m;    
cin >> t >> m;    
for(int i = 1; i <= m; i++) 
{        
int a, b;        
cin >> a >> b;        
    for(int j = 1; j <= t; j++) 
    { 
    if(j >= a)                
    dp[i][j] = max(dp[i-1][j], dp[i-1][j-a] + b);            
    else                
    dp[i][j] = dp[i-1][j];        
    }    
}    
cout << dp[m][t];    
return 0; 
}

一次元配列を用いて問題を解き,状態圧縮後,f[v]をv kgを超えない最大値とすると,f[v]=max(f[v],f[v-w[i]+c[i]),v>=w[i],1<=i<=nとなる.

#include
#include
using namespace std;
const int maxm = 2001, maxn = 101;
int m, n;
int w[maxn], c[maxn];
int f[maxm]; 
int main()
{
    scanf("%d%d",&m, &n);            //    m     n
    for (int i=1; i <= n; i++)
        scanf("%d%d",&w[i],&c[i]);     //          
    for (int i=1; i <= n; i++)             // f(v)       v       
        for (int v = m; v >= w[i]; v--)  //     
            f[v] = max(f[v-w[i]]+c[i], f[v]);
    printf("%d
",f[m]);                      // f(m)    
    return 0;
}

完全なリュックサック問題
N種類の品物とV容量のリュックサックがあり、それぞれの品物には無限のものがあります.第i種の物品の費用はw[i]、価値はc[i]である.リュックサックにどのアイテムを入れるかを解くと、これらのアイテムの費用の合計がリュックサックの容量を超えず、価値の合計が最大になります.
完全リュックと01リュックはよく似ていて、違いは完全リュックの品物が無限にあることです.前の選択から選択しないかを選択しないかに変えて、いくつかを選択します.
01リュックサックと同じように、状態遷移方程式を書くことができます.

     f[i][v]=max(f[i-1][v-k*c[i]]+k*w[i] | 0<=k*c[i]<=v)

もう一つ簡単な最適化↓_↓
ある品物の価値が別の品物の価値より小さいが、価格が別の品物より高い場合、私たちはこの品物を考えなくてもいい.すなわち、2つの物品i,jがc[i]<=c[j]を満たし、w[i]>=w[j]であれば、物品jを除去し、考慮しない.私たちはどうして高くてまずいものを買うのですか(′▽`)

#include
#include
using namespace std;
const int maxm=2001,maxn=101;
int n,m,v,i;
int c[maxn],w[maxn];
int f[maxm];
int main()
{
    scanf("%d%d",&m,&n);            //    m     n
    for(i=1;i<=n;i++) 
        scanf("%d%d",&w[i],&c[i]);
    for(i=1;i<=n;i++)
        for(v=w[i]; v<=m; v++)          //  f[v]       v       
                                        //   v++       01   
            f[v]=max(f[v-w[i]]+c[i], f[v]);
    printf("%d
", f[m]);           // f[m]    
    return 0;
}

多重リュックサック問題
N種類の品物とV容量のリュックサックがあります.第i種の物品は最大n[i]件が利用可能であり、1件当たりの費用はw[i]、価値はc[i]である.リュックサックにどのアイテムを入れるかを解くと、これらのアイテムの費用の合計がリュックサックの容量を超えず、価値の合計が最大になります.
ここにはもう一つの制限条件があり、各品物が利用可能な回数を規定しています.
同様に,状態遷移方程式を導くことができる:f[i][v]=max(f[i−1][v−kw[i]+kc[i]|0<=k<=n[i])
【問題の説明】
クラスが学校の運動会で全校1位の成績を収めたことを祝うため、担任は祝賀会を開くことを決め、そのために賞品を買って選手をねぎらうことにした.最大価値の賞品を購入できる金額を期待し、精力と体力を補うことができます.
【入力形式】
1行目の2つの数n(n<=500)、m(m<=6000)で、nは購入したい賞品の数を表し、mは送金金額を表す.次にn行は、各行3個分、v,w,sは、それぞれI番目の賞品の価格、価値(価格と価値が異なる概念)と購入数(0個からs個まで可能)を表し、そのうちv<=100、w<=1000、s<=10である.
【出力形式】
1行目:1つの数で、今回の購入で得られる最大の価値を表します(注意!価格ではありません).
【入力サンプル】
5 1000
80 20 4
40 50 9
30 50 7
40 30 6
20 20 1
【出力サンプル】
1040

#include
#include
using namespace std;
int v[6002], w[6002], s[6002];
int f[6002];
int n, m;
int main()
{
    scanf("%d%d",&n,&m);
    for (int i = 1; i <= n; i++)
        scanf("%d%d%d",&v[i],&w[i],&s[i]);
    for (int i = 1; i <= n; i++)
       for (int j = m; j >= 0; j--)
          for (int k = 0; k <= s[i]; k++)
          {
               if (j-k*v[i]<0) break;
               f[j] = max(f[j],f[j-k*v[i]]+k*w[i]);
          }
    printf("%d
",f[m]);
    return 0;
}

dp圧縮後

#include
#include
using namespace std;
int v[10001],w[10001];
int f[6001];
int n,m,n1;
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        int x,y,s,t=1;
        scanf("%d%d%d",&x,&y,&s);
        while (s>=t) 
        {
            v[++n1]=x*t;
            w[n1]=y*t;
            s-=t;
            t*=2;
        }
        v[++n1]=x*s;
        w[n1]=y*s;                             // s 2     ：1，2，4，…，2^(k-1)，s-2^k+1,
    }
for(int i=1;i<=n1;i++)
        for(int j=m;j>=v[i];j--)
           f[j]=max(f[j],f[j-v[i]]+w[i]); 
    printf("%d
",f[m]);
    return 0;
}

TIP:ちょうどいっぱいなら

二次元配列f 0][0]は0に設定され、その他は-INFに設定されている.

次元配列f[0]は0であり、その他は-INFである.

このブログの説明を復習してください.http://www.cnblogs.com/fengziwei/p/7750849.html