C++解決背包問題

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

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

問題描述:

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

思路:

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

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

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

綜上所述，本題的狀態轉移方程為： f [ i ] [ j ] = m a x f [ i ? 1 ] [ j ? w [ i ] ] + v [ i ] ， f [ i ? 1 ] [ j ] f[i][j]=max{f[i-1][j-w[i]]+v[i]，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 ) O(V) O(V)，

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

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

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

也就是說，原先的 f [ i ? 1 ] [ j ? w [ i ] ] f[i-1][j-w[i]] f[i?1][j?w[i]]已經被覆寫了，現在里面裝的是 f [ i ] [ j ? w [ i ] ] f[i][j-w[i]] f[i][j?w[i]]，這時極有可能已經選中了物品 i i i，如果這次物品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 N N個物品和一個容量為 S S S的背包，第 i i i件物品的重量是 w [ i ] w[i] w[i]，價值是 v [ i ] v[i] v[i]，在每種物品有無限個，不可拆分，不超過背包容量的前提下，問如何才能讓背包的總價值最大，

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

想想看，0-1背包在哪里阻止了重復選擇物品的可能？

當然是 j j j的回圈這個地方！

那么，我們直接把 j 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 N N個物品和一個容量為 S S S的背包，第 i i i件物品的重量是 w [ i ] w[i] w[i]，價值是 v [ i ] v[i] v[i]，上限是 c [ i ] c[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