リュック問題まとめその0/1リュック

0/1リュックサック
導入テーマ:N品とV容量のリュックサックがあります.第iの物品の費用(すなわち体積、以下同じ)はw[i]であり、価値はc[i]である.どの物品をリュックサックに入れると、これらの物品の費用の合計がリュックサックの容量を超えず、かつ価値の合計が最大になるかを解く.

1.         ，              
2.         ，         

そして、状態遷移方程式

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

説明:f[i][v]は、前のiつのアイテムを容量vのリュックサックに入れる最大の価値を表し、私たちができる決定に基づいているので、現在のアイテムを入れるか、現在のアイテムを入れるかを選択しないかを比較すればより優れている.(i-1)は、前の既知の状態が現在の状態に押され、物を入れないのは[v]または[v-w[i]]で表される.
に注意
なぜ状態遷移方程式はf[i][v]=max f[i-1][v],f[i-1][v-w[i]+c[i]=f[i][v]=f[i-1][v-w[i]]ではないのか.
f[i][v]有意義であり、かつ1つの前のiつの物品のサブセットが存在する場合にのみ、その費用の合計はvである.したがって,後者の方程式に従って繰返しが完了すると,最終的な答えはf[N][V]とは限らず,f[N][0...V]の最大値となる.状態の定義の「恰」の字を外す(すなわちリュックサックを満タンにするかどうか)と、移行方程式にf[i-1][v]をもう1つ加えることで、f[N][V]が最後の答えであることが保証される.しかし、すべてのf[i][j]の初期値を0に割り当てると、f[n][v]も最後の答えになることがわかります.どうしてですか.これにより、最初のf[i][j]が有意義であることを黙認し、価値が0であるだけで、無物放のリュックサックの価値が0であると見なされるため、最終的な価値に影響を及ぼさず、初期化後の状態表示で「恰」の字を消すことができる.
ぎじふごう

for 1...N
    for 1...V
        f[i][v] = max (f [i-1] [v] , f [i-1] [v - w [i] ] + c[i]);

コード実装

#include
using namespace std;
const int maxm = 201, maxn = 31;
int m, n;
int w[maxn], c[maxn];
int f[maxn][maxm]; 

int max(int x,int y){
x > y ? x : y;
}  // x y   

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[i][v]   i   ，      v     
        for (int v = m; v > 0; v--)
            if (w[i] <= v)  f[i][v] = max(f[i-1][v],f[i-1][v-w[i]]+c[i]);
            else  f[i][v] = f[i-1][v];
     printf("%d",f[n][m]);        // f[n][m]    
     return 0;
}

このコードを観察すると,その時間的および空間的複雑さはいずれもO(N*V)であることが容易に分かった.サイクルによってすべての物品が遍歴された(各物品が1回しか遍歴されていない)ため,時間的に最適化することは困難である.次に,空間的最適化を考慮すると,空間的に最大O(V)まで最適化できる.
まず、上記の基本構想がどのように実現されるかを考えると、主サイクルi=1...Nがあり、2次元配列f[i][0...V]のすべての値が算出されるに違いない.では、1つの配列f[0...V]だけで、i回目のサイクル終了後のf[v]に私たちが定義した状態f[i][v]が表示されることを保証できるだろうか.f[i][v]は、f[i-1][v]とf[i-1][v-w[i]]の2つのサブ問題から渡されたものであり、f[i][v]を押すとき(すなわち、i回目のメインサイクルでf[v]を押すとき)にf[i-1][v]とf[i-1][v-w[i]]の値が得られることを保証できるだろうか.実際には、これは、メインサイクルのたびにv=V...0の逆順序でf[v]を押すことを保証し、f[v]を押すときにf[v-w[i]]が状態f[i-1][v-w[i]]の値を保存することを保証することができる.
このうちf[v]=max{f[v],f[v-w[i]+c[i]}は遷移方程式f[i][v]=max{f[i-1][v],f[i-1][v-w[i]+c[i]}に相当する.現在のf[v-w[i]]は元のf[i-1][v-w[i]]に相当するからである.vのループ順序を上の逆順から順序に変更すると,f[i][v]はf[i][v-w[i]]から推測され,本題とは意味が異なるが,もう一つの重要な完全リュック問題の最も簡便な解決策であるため,学習は1次元配列だけで01リュック問題を解く必要がある.
ぎじふごう

for i=1..N 
    for v=V..0 
        f[v]=max (f[v],f[v-w[i]]+c[i]); 

数学モデル

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

コード実装の最適化

#include
using namespace std;

const int maxm = 2001, maxn = 31;
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--)
           if (f[v-w[i]]+c[i]>f[v])
              f[v] = f[v-w[i]]+c[i];
    printf(“%d”,f[m]);            //f(m)    
    return 0;
}

小结:0/1リュックサックはリュックサックの基础で、0/1リュックサックを掌握することはすべてのリュックサックの问题を掌握することに対して基础を筑きます.0/1リュックサックは問題の通解です.つまり、それぞれのアイテムを1つだけリュックに入れることができます.多くの問題をブラシして、テンプレートを記憶して、0/1リュックサックの問題は簡単に解決することができます~