乘法原理

百度百科

乘法原理是說把多個步驟的所有方法相乘，表示整個事件所有可能的解決方法

原題

有?N�?種物品和一個容量是?V�?的背包。

第?i�?種物品最多有?si��?件，每件體積是?vi��，價值是?wi��。

求解將哪些物品裝入背包，可使物品體積總和不超過背包容量，且價值總和最大。
輸出最大價值。

輸入格式

第一行兩個整數，N，V�，�，用空格隔開，分別表示物品種數和背包容積。

接下來有?N�?行，每行三個整數?vi,wi,si��,��,��，用空格隔開，分別表示第?i�?種物品的體積、價值和數量。

輸出格式

輸出一個整數，表示最大價值。

數據范圍

0<N≤10000<�≤1000
0<V≤20000<�≤2000
0<vi,wi,si≤20000<��,��,��≤2000

提示：

本題考查多重背包的二進制優化方法。

輸入樣例

4 5
1 2 3
2 4 1
3 4 3
4 5 2

輸出樣例：

10

難度：中等

時/空限制：1s / 64MB

總通過數：75903

總嘗試數：164479

來源：背包九講 , 模板題

算法標簽

---

挑戰模式

原題鏈接

傳送門?

代碼

#include<bits/stdc++.h>
using namespace std;const int N=11000+10,M=2000+10;
int v[N],w[N];
int f[M];int main()
{int n,m;scanf("%d%d",&n,&m);int cnt=0;for(int i=0;i<n;i++){int a,b,s;scanf("%d%d%d",&a,&b,&s);int k=1;while(k<=s){cnt++;v[cnt]=k*a;w[cnt]=k*b;s-=k,k*=2;}if(s>0){cnt++;v[cnt]=s*a;w[cnt]=s*b;}}n=cnt;for(int i=1;i<=n;i++){for(int j=m;j>=v[i];j--){f[j]=max(f[j],f[j-v[i]]+w[i]);}}printf("%d\n",f[m]);return 0;
}

總結

一、二進制優化

?1.不優化的情況的時間復雜度是N^3，在數據范圍比較大的時候會超時，所以我們選擇二進制優化，把一維的N優化為logN，時間復雜度變為N^2*logN，可以通過這道題

2.思路是，給定了物品數目s,可以選擇0件，1件，2件，……，s件物品，一個一個循環的話需要循環s+1次才能表示所有的情況，如果我們使用二進制的話，int范圍內都只需要32位數字，就可以表示所有數字，數據范圍是2000，只需要最多11個數字，2^11=2048，2^0,2^1,2^2,...2^11,二進制表示本質和01背包就很相似，每一個數位選擇0或者是1，從而可以表示所有數字

3.注意一個一般化的情況，物品的件數s不是2的整數次冪，比如數字10，2^0=1,2^1=2,2^2=4,2^3=8,0+1+2+4+8>10,如果選擇到數字2^3=8，超過了我們最多可以選擇的件數10，這會造成理論上可以選擇多件物品，但是實際上只有10件物品可以選擇，所以我們只能選擇到2^2=4,0+1+2+4=7,再補充一個數字10-7=3,原來的0，1，2，4可以表示0~7范圍的所有數字，加上數字3之后，可以表示0~10范圍的所有數字，0，1，2，4表示0~7范圍內所有數字的方法就是二進制計數，每一個數位是否選擇該數字

- - - -：000? ? ? ? 0? ? ? ? 0

- - - - ：001? ? ? ? 1? ? ? ? 1

- - - -：010? ? ? ? 2? ? ? ? 2

- - - -：011? ? ? ? 3? ? ? ? 1+2

- - - -：100? ? ? ? 4? ? ? ? 4

- - - -：101? ? ? ? 5? ? ? ? 4+1

- - - - ：110? ? ? ? 6? ? ? ? 4+2

- - - - ：111? ? ? ? 7? ? ? ? 4+2+1

二、代碼細節

1.表示物品的數組的容量是 1000*11（二進制優化），表示答案的數組的容量是2000，都增加10防止數組越界

2.本質是把一件物品拆成多組物品，是否選擇該組物品，從而把多重背包轉換成01背包來進行求解

3.用一個計數器來存數組下標，和單鏈表的dix類似，while循環之后加一個if特判，表示最后一種情況，和質因數分解類似，也是判斷最后處理的結果

4.原來的n件物品變成了現在的cnt件物品，因為計數器從1開始作為數下標存儲物品的體積和價值，所以套用01背包模板的時候要從1開始遍歷，01背包模板的第二層循環體積從大到小遍歷