C++解決揹包問題

感謝https://blog.csdn.net/Hearthougan/article/details/53869671

只許選一次的揹包 –– 0-1揹包

問題描述:

有$N$個物品和一個容量為$S$的揹包，第$i$件物品的重量是$w[i]$，價值是$v[i]$。在每種物品只許放一次，不可拆分，不超過揹包容量的前提下，問如何才能讓揹包的總價值最大。

思路:

我們將$f[i][j]$定義為在前$i$個物品裡做出選擇，使容量為$j$的揹包價值最大。

對於第$i$件物品，有兩種情況:

1.放物品i，此時$f[i][j]=f[i-1][j-w[i]]+v[i]$
2.不放物品i，此時$f[i][j]=f[i-1][j]$

綜上所述，本題的狀態轉移方程為：$f[i][j]=maxf[i-1][j-w[i]]+v[i]，f[i-1][j]$。

虛擬碼如下：

for 1...n
    for w[i]...s
        f[i][j]=max{f[i-1][j-w[i]]+v[i]，f[i-1][j]}

這個思路時間上是最優的，但是空間可以優化到$O(V)$。

畢竟$f[i][j]$只跟上一行有關係，那麼我們可以試試只用一維陣列去儲存。

這種方法可不可行？可行，但是j要逆向列舉，因為舊資料不能被覆蓋。

因為$f[j]$依賴於$f[j-w[i]]$（舊資料哦），如果正向列舉的話，$f[j-w[i]]$就已經被新資料覆蓋掉了，就有可能已經選入了物品i！（別忘了$f[i][j]$是指在前i個物品裡做出選擇）

也就是說，原先的$f[i-1][j-w[i]]$已經被覆蓋了，現在裡面裝的是$f[i][j-w[i]]$。這時極有可能已經選中了物品$i$，如果這次物品i還被選中的話，物品$i$就被選中了兩次，違背了0-1揹包的限制！

因此，為了不違背0-1揹包的限制，我們必須逆向列舉。

優化後的虛擬碼如下:

for 1...n
    for s...w[i]
           f[j]=max{f[j-w[i]]+v[i],f[j]}

例題：

開心的金明

金明今天很開心，家裡購置的新房就要領鑰匙了，新房裡有一間他自己專用的很寬敞的房間。更讓他高興的是，媽媽昨天對他說：「你的房間需要購買哪些物品，怎麼佈置，你說了算，只要不超過N元錢就行」。今天一早金明就開始做預算，但是他想買的東西太多了，肯定會超過媽媽限定的N元。於是，他把每件物品規定了一個重要度，分為5等：用整數1~5表示，第5等最重要。他還從因特網上查到了每件物品的價格（都是整數元）。他希望在不超過N元（可以等於N元）的前提下，使每件物品的價格與重要度的乘積的總和最大。

設第j件物品的價格為v[j]，重要度為w[j]，共選中了k件物品，編號依次為j1...jk，則所求的總和為：v[j1]*w[j1]+..+v[jk]*w[jk]。

請你幫助金明設計一個滿足要求的購物單。

【輸入格式】
輸入的第1行，為兩個正整數N,M，用一個空格隔開：（其中n（n<30000）表示總錢數，m(m<25)為希望購買物品的個數。）

從第2 行到第m+1行，第j行給出了編號為j-1的物品的基本資料，每行有2個非負整數v，p
（其中v 表示該物品的價格（v≤10000），p 表示該物品的重要度（1~5）） 

【輸出格式】
輸出只有一個正整數，為不超過總錢數的物品的價格與重要度乘積的總和的最大值（<100000000）。

【輸入樣例】
1000 5
800 2
400 5
300 5
400 3
200 2
【輸出樣例】
3900

程式碼：

#include<iostream>
#include <algorithm>
using namespace std;
struct thing {
   int v,p;
} want[30];
long long c[10010],d[10010];
int main() {
   int n,m;
   cin>>n>>m;
   for(int i=1; i<=m; i++) {
       cin>>want[i].v>>want[i].p;
   }
   for(int i=1; i<=m; i++) {
       for(int j=n; j>=want[i].v; j--) {
           c[j]=max(c[j],c[j-want[i].v]+want[i].v*want[i].p);
       }
   }
   cout << c[n] << endl;
   return 0;
}

可以選無數次的揹包 –– 完全揹包

問題描述：

有$N$個物品和一個容量為$S$的揹包，第$i$件物品的重量是$w[i]$，價值是$v[i]$。在每種物品有無限個，不可拆分，不超過揹包容量的前提下，問如何才能讓揹包的總價值最大。

此題和0-1揹包問題很像，所以可以在0-1揹包的基礎上做一定的修改就可以了。

想想看，0-1揹包在哪裡阻止了重複選擇物品的可能？

當然是$j$的迴圈這個地方！

那麼，我們直接把$j$的迴圈這個地方改成正序（可能重複裝入物品，正好滿足要求）不就可以了嗎？

完整程式碼如下（找不到例題QAQ）

#include<iostream>
#include<algorithm>
using namespace std;
struct thing { 
   int v,p;
} want[30];
long long c[10010];
int main() { 
   int n,m,;    
   cin>>n>>m;    
   for(int i=1; i<=m; i++) { 
          cin>>want[i].v>>want[i].p;    
    }    
    for(int i=1; i<=m; i++) {        
        for(int j=want[i].v;j<=n; j++) {          
            c[j]=max(c[j],c[j-want[i].v]+want[i].p);       
          }   
      }    
      cout << c[n] << endl; 
      return 0;
}

數量有上限的揹包 –– 多重揹包

問題描述：有$N$個物品和一個容量為$S$的揹包，第$i$件物品的重量是$w[i]$，價值是$v[i]$，上限是$c[i]$。在不可拆分，不超過揹包容量的前提下，問如何才能讓揹包的總價值最大。

此題和0-1揹包問題也很像，所以也可以在0-1揹包的基礎上做一定的修改。

我們可以直接加一個迴圈，從0到上限列舉物品個數，虛擬碼如下：

for 1...n 
   for s...w[i]  
       for 0...c[i]
         if j>=w[i]*k
          f[j]=max{f[j-w[i]*k]+v[i]*k,f[j]}

例題：

慶功會

為了慶祝班級在全校運動會上取得全校第一名的成績，班主任決定開一場慶功會，為此撥款購買獎品犒勞運動員。期望撥款金額能夠買最大值的獎品，可以補充他們的精力和體力。
【輸入格式】
第一行兩個數n（≤500），m（≤6000），分別代表獎品種數和撥款金額。
接下來n行，每行三個數v，p，s，分別代表獎品價格，價值和能夠買到的最大數量，其中v≤100，p≤1000，s≤10。
【輸出格式】
一個數，表示此次購買能獲得的最大價值。
【輸入樣例】
5 1000
80 20 4
40 50 9
30 50 7
40 30 6
20 20 1
【輸出樣例】
1040

#include<iostream>
#include<algorithm>
using namespace std;
struct thing { 
  int v,p,s;
} want[30];
long long c[10010];
int main() { 
  int n,m;       
  cin>>n>>m;      
  for(int i=1; i<=m; i++) {
             cin>>want[i].v>>want[i].p>>want[i].s;        
  }        
  for(int i=1; i<=n; i++) { 
     for(int j=m;j>=want[i].v; j--) {
         for(int k=0;k<=want[i].s; k++){
              if(j >=k*want[i].v)
                 c[j]=max(c[j],c[j-k*want[i].v]+k*want[i].p);      
         }          
      }       
   }          
   cout << c[m] << endl;      
   return 0;
}

附：
0-1揹包空間和時間都最優的程式碼

#include <iostream>
#include <algorithm>
using namespace std;
int main(){
    int n,s,f[100],w,v;
    cin>>n>>s;
    for(int i = 1;i <= n;i++)
        cin>>w>>v;
        for(int j = s; j >= w[i]; j--)
            f[j] = max(f[j], f[j-w]+v);
    cout<<f[s]<<endl;
    return 0;
}

超級大禮包
https://www.luogu.com.cn/discuss/show/263072