博客推行版本更新，成果積累制度，已經寫過的博客還會再次更新，不斷地琢磨，高質量高數量都是要追求的，工匠精神是學習必不可少的精神。因此，大家有何建議歡迎在評論區踴躍發言，你們的支持是我最大的動力，你們敢投，我就敢肝 ...
多重背包也是一種基本的背包問題模型，其基本特點是：每種物品有一個固定的裝入次數上限。
多重背包問題的一般描述為：有N個物品，第i個物品的重量與價值分別為W[i]與P[i]且第i種物品最多有C[i] 件。背包容量為V，試問在每個物品不超過其上限的件數（物品必須保持完整）的情況下，如何讓背包裝入的物品具有更大的價值總和。
其一般解題思路為：
設f[i][j] 表示從編號1~i的物品中挑選任意數量的任意物品放入容量為j的背包中得到的最大價值，那麼有 f[i][j]=max { f[i−1][j−k∗w[i]]+k∗v[i] ∣0≤k≤p[i]&k∗w[i]≤j }。
編寫代碼時，可以寫成如下的迴圈。
for ( i = 1; i <= N; i++)
for ( j = 1; j <= V; j++)
for (k = 0; k <= C[i] && k * W[i] <= j; k++)
{
f[i][j] = max( f[i][j], f[i - 1][j - k * W[i]] + k *P[i]);
}
求得的最優值為f[N][V]。
同樣多重背包也可以進行空間優化，將二維數組優化為一維數組，即
f[j]=max { f[j]，f[j−k∗W[i]]+k∗P[i] } （0≤k && k∗W[i]≤j）
編寫代碼時，一般採用如下的迴圈。
for (i=1; i<=N; i++)
for (j=V; j>=0; j--)
for (k=0; k<=c[i] && k*W[i] <=j; k++)
f[j] = max( f[j], f[j - k * W[i]] + k *P[i]);
求得的最優值為f[V]。
從上面的程式代碼可以看出，多重背包的處理一般採用三重迴圈，時間複雜度較高。為了對時間進行優化，可以採用二進位優化法將多重背包轉變為0/1背包（採用二重迴圈）進行處理。
所謂二進位優化法就是將第 i 種c[i]件物品按二進位的方法分拆成s份“不同”的物品。例如，設第i件物品有20件，每件重量和價值分別為w和p，則可以分拆別5份“物品”如下：
第1份含有1件物品，重量為w，價值為p；
第2份含有2件物品，重量為2w，價值為2p；
第3份含有4件物品，重量為4w，價值為4p；
第4份含有8件物品，重量為8w，價值為8p；
第5份含有5件物品，重量為5w，價值為5p。
因為，1+2+4+8+5=20，則由這5份“物品”可組合成0~20件之間任意件數的物品。這5份“物品”在進行組合時，每份物品要麼選取，要麼不選取，正好就是對這5份物品進行0/1背包處理。由此，多重背包可以通過這種方式轉化為0/1背包進行處理。從而將三重迴圈優化為二重迴圈處理。
我們知道，k位二進位數可以表示0~2k-1之間的任意整數，k位二進位數從低位到高位，各位上的權值依次為1（20）、2（21）、4（22）、…、2k-1。因此，對於任意一個正整數x，則可以將其拆分為1+2+4+…+2k-1+y（其中y是二進位拆分剩餘的部分，y<2k）。
通過拆分後，就可以將多重背包問題轉換為0/1背包問題求解了。
編寫代碼如下：
for (i=1; i<=N; i++)
{
int s =C[i];
for (j=1; j<=s; s-=j, j=j*2) // 二進位拆分
{
for (k =V; k >=0 && k>= j*W[i]; k--) // 0/1背包
{
f[k] = max(f[k], f[k - j*W[i]] + j *P[i]);
}
}
if (s > 0) // 拆分的剩餘部分
{
for ( j =V; j >= s * W[i]; j--)
{
f[j] = max(f[j], f[j - s * W[i]] + s * P[i]);
}
}
}
【例1】購買糧食
問題描述
你準備自己採購一些糧食支援災區，現在假設你一共有資金n元，而市場有m種大米，每種大米都是袋裝產品，其重量和價格不等，並且只能整袋購買。
請問：你用有限的資金最多能採購多少公斤糧食呢？
輸入
輸入數據首先包含一個正整數C，表示有C組測試用例，每組測試用例的第一行是兩個整數n和m（1<=n<=100，1<=m<=100），分別表示經費的金額和大米的種類，然後是m行數據，每行包含3個數p，h和c（1<=p<=20,1<=h<=200,1<=c<=20），分別表示每袋的價格、每袋的重量以及對應種類大米的袋數。
輸出
對於每組測試數據，請輸出能夠購買大米的最多重量，你可以假設經費買不光所有的大米，並且經費你可以不用完。每個實例的輸出占一行。
輸入樣例
1
8 2
2 100 4
4 100 2
輸出樣例
400
（1）編程思路。
典型的多重背包問題。按上面介紹的方法，採用二維數組編寫源程式1；採用一維數組編寫源程式2；採用二進位優化的方法編寫源程式3。
（2）採用二維數組編寫的源程式1。
#include <stdio.h> #include <string.h> int max(int a,int b) { return a>b?a:b; } int main() { int p[105],h[105],c[105],f[105][105]; int t; scanf("%d",&t); while (t--) { int n,m; scanf("%d%d",&n,&m); int i,j,k; for (i=1;i<=m;i++) scanf("%d%d%d",&p[i],&h[i],&c[i]); memset(f,0,sizeof(f)); for (i=1;i<=m;i++) for (j=1; j<=n; j++) for (k=0; k<=c[i] && k*p[i] <=j; k++) f[i][j]=max(f[i][j],f[i-1][j-k*p[i]]+k*h[i]); printf("%d\n",f[m][n]); } return 0; }
（3）採用一維數組編寫的源程式2。
#include <stdio.h> #include <string.h> int max(int a,int b) { return a>b?a:b; } int main() { int p[105],h[105],c[105],f[105]; int t; scanf("%d",&t); while (t--) { int n,m; scanf("%d%d",&n,&m); int i,j,k; for (i=1;i<=m;i++) scanf("%d%d%d",&p[i],&h[i],&c[i]); memset(f,0,sizeof(f)); for (i=1;i<=m;i++) for (j=n;j>=0;j--) for (k=0; k<=c[i] && k*p[i] <=j; k++) f[j]=max(f[j],f[j-k*p[i]]+k*h[i]); printf("%d\n",f[n]); } return 0; }
（4）採用二進位優化的方法編寫的源程式3。
#include <stdio.h> #include <string.h> int max(int a,int b) { return a>b?a:b; } int main() { int p[105],h[105],c[105],f[105]; int t; scanf("%d",&t); while (t--) { int n,m; scanf("%d%d",&n,&m); int i,j,k; for (i=1;i<=m;i++) scanf("%d%d%d",&p[i],&h[i],&c[i]); memset(f,0,sizeof(f)); for (i=1; i<=m; i++) { int s =c[i]; for (j=1; j<=s; s-=j, j=j*2) // 二進位拆分 { for (k =n; k >=0 && k>= j*p[i]; k--) // 0/1背包 { f[k] = max(f[k], f[k - j*p[i]] + j *h[i]); } } if (s > 0) // 拆分的剩餘部分 { for ( j =n; j >= s * p[i]; j--) { f[j] = max(f[j], f[j - s * p[i]] + s * h[i]); } } } printf("%d\n",f[n]); } return 0; }
【例2】擺花
問題描述
小明的花店新開張，為了吸引顧客，他想在花店的門口擺上一排花，共m盆。通過調查顧客的喜好，小明列出了顧客最喜歡的n種花，從1到n標號。為了在門口展出更多種花，規定第i種花不能超過 ai盆，擺花時同一種花放在一起，且不同種類的花需按標號的從小到大的順序依次擺列。
試編程計算，一共有多少種不同的擺花方案。
輸入
第一行包含兩個正整數n和m（0<n≤100，0<m≤100），中間用一個空格隔開。
第二行有n個整數，每兩個整數之間用一個空格隔開，依次表示 a1,a2,…,an。
輸出
一個整數，表示有多少種方案。註意：因為方案數可能很多，請輸出方案數對 10^6+7取模的結果。
輸入樣例
2 4
3 2
輸出樣例
2
（1）編程思路。
典型的多重背包問題。按前面的介紹進行處理即可。
採用二維數組，定義int f[105][105]={0}。設f[i][j]表示前i種花中擺放j盆花的方案數，初始值初f[0][0]=1（什麼也不擺）外，其餘全部為0。可以編寫如下的源程式1。
採用一維數組，int f[105]={0}；設f[i]表示擺放i盆花的方案數。可以編寫如下的源程式2。
（2）使用二維數組編寫的源程式1。
#include <stdio.h> int main() { int f[105][105]={0},a[105]; int n,m; scanf("%d%d",&n,&m); int i,j,k; for (i=1; i<=n; i++) { scanf("%d",&a[i]); } f[0][0]=1; for (i=1; i<=n; i++) for (j=0; j<=m; j++) for (k=0; k<=(a[i]<j?a[i]:j); k++) f[i][j] = (f[i][j] + f[i-1][j-k])%1000007; printf("%d\n",f[n][m]); return 0; }
（3）使用一維數組編寫的源程式2。
#include <stdio.h> int main() { int f[105]={0},a[105]; int n,m; scanf("%d%d",&n,&m); int i,j,k; for (i=1; i<=n; i++) scanf("%d",&a[i]); f[0] = 1; for (i=1; i<=n; i++) for (j=m; j>=0; j--) for (k=1; k<=(a[i]<j?a[i]:j); k++) f[j] = (f[j] + f[j-k])%1000007; printf("%d\n",f[m]); return 0; }
將上面的源程式1和2提交給洛谷題庫P1077 [NOIP2012 普及組] 擺花（https://www.luogu.com.cn/problem/P1077），測評結果均為“Accepted”。
【例3】收集櫻花
問題描述
有k棵櫻花樹，在第i棵樹下最多能收集到 si朵櫻花（收集了0朵櫻花也算收集了櫻花）。
你有多少種方案能夠收集到恰好n朵櫻花呢？
輸入
第一行兩個正整數 n,k，表示要收集n朵櫻花，有k棵櫻花樹。
接下來一行k個正整數 s1,s2,…,sk，其中 si表示最多在第i棵櫻花樹下收集到si朵櫻花。
輸出
一行一個整數，表示恰好收集到n朵櫻花的方案數。
由於答案可能太大，請輸出答案對 10086001 取模後的值。
特殊地，如果收集不到n朵櫻花，請輸出一個字元串 impossible。
輸入樣例#1
3 4
1 1 1 1
輸出樣例 #1
5
輸入樣例 #2
10 9
9 6 8 7 9 6 5 4 3
輸出樣例#2
68345
輸入樣例 #3
10 5
2 2 2 2 1
輸出樣例 #3
Impossible
（1）編程思路1。
定義二維數組int f[5001][5001]；其中f[i][j]表示前i顆櫻花樹下共收集到j朵櫻花的方案數。顯然，有f[i][0]=1（1≤i≤n，每顆樹下可不收集櫻花，收集了0朵櫻花也算收集了櫻花，方案數為1），還有f[1][j]=1（1≤j≤s[1]，第1顆櫻花樹下可分別收集1~s[1]朵櫻花）。
轉移方程為： f[i][j]=f[i][j]+f[i-1][j-k] （其中k值為第i可櫻花樹收集櫻花的朵數）。
（2）源程式1。
#include <stdio.h> #include <string.h> int f[5001][5001]={0}; int main() { int v,n; scanf("%d%d",&v,&n); int s[5001]; int i,j,k; int tot=0; for (i=1;i<=n;i++) { scanf("%d",&s[i]); tot+=s[i]; } if (tot<v) { printf("impossible\n"); return 0; } for (i=1;i<=n;i++) f[i][0]=1; for (i=1;i<=s[1];i++) f[1][i]=1; for (i=2; i<=n; i++) { for (j=1; j<=v; j++) { for (k=0; k<=s[i] && k<=j; k++) { f[i][j]=(f[i][j]+f[i-1][j-k])%10086001; } } } int ans=0; for (i=1; i<=n; i++) ans = (ans+f[i][v])%10086001; printf("%d\n",ans); return 0; }
將上面的源程式1提交給洛谷題庫P6394 櫻花，還有你（https://www.luogu.com.cn/problem/P6394），測評結果為“Unaccepted”，其中測試點#17、測試點#19和測試點#20，顯示“TLE”，測試點#18顯示“MLE”。
（3）編程思路2。
由於數據量較大，因此採用二維數組存儲，會存在超記憶體限制的情況，因此採用一維數組進行處理。
（4）源程式2。
#include <stdio.h> #include <string.h> int f[5001]={0}; int main() { int v,n; scanf("%d%d",&v,&n); int s[5001]; int i,j,k; int tot=0; for (i=1;i<=n;i++) { scanf("%d",&s[i]); tot+=s[i]; } if (tot<v) { printf("impossible\n"); return 0; } f[0]=1; int ans=0; for (i=1;i<=n;i++) // 前i棵樹 { for (j=v;j>=0;j--) for (k=1;k<=s[i] && k<=j;k++) f[j]=(f[j]+f[j-k])%10086001; ans=(ans+f[v])%10086001; } printf("%d\n",ans); return 0; }
將上面的源程式2提交給洛谷題庫P6394 櫻花，還有你（https://www.luogu.com.cn/problem/P6394），測評結果仍為“Unaccepted”，其中測試點#17、測試點#18、測試點#19和測試點#20，均顯示“TLE”。
（5）編程思路3。
源程式2中的多重背包採用三重迴圈實現，由於數據量較大，迴圈處理太耗時，因此會超時。觀察第三層迴圈，每次的f[j]都是加上一個區間，所以可以直接用一個首碼和來計算，這樣第三層迴圈就可以省掉了。
（6）源程式3。
#include <stdio.h> int main() { int v,n; scanf("%d%d",&v,&n); int f[5001]={0}; int s[5001]; int sum[5001]={0}; // 保存首碼和 int i,j; int tot=0; for (i=1;i<=n;i++) { scanf("%d",&s[i]); tot+=s[i]; } if (tot<v) { printf("impossible\n"); return 0; } sum[0]=f[0]=1; int ans=0; for (i=1;i<=n;i++) // 前i棵樹 { for (j=1;j<=v;j++) // 更新首碼和 sum[j]=(sum[j-1]+f[j])% 10086001; for (j=v;j>=1;j--) { int k=s[i]<j?s[i]:j; if (k==j) f[j]=(f[j]+sum[j-1])% 10086001; else f[j]=(f[j]+sum[j-1]-sum[j-k-1]+10086001)% 10086001; //利用首碼和 } ans=(ans+f[v])%10086001; } printf("%d\n",ans); return 0; }
將上面的源程式3提交給洛谷題庫P6394 櫻花，還有你（https://www.luogu.com.cn/problem/P6394），測評結果為“Accepted”。
【例4】砝碼稱重
問題描述
設有1g、2g、3g、5g、10g、20g的砝碼各若幹枚（其總重≤1000），計算用這些砝碼能稱出的不同重量的個數N，但不包括一個砝碼也不用的情況。
輸入
輸入方式：a1 , a2 ,a3 , a4 , a5 ,a6（表示1g砝碼有a1個，2g砝碼有a2個，…，20g砝碼有a6個）。
輸出
輸出方式：Total=N
輸入樣例
1 1 0 0 0 0
輸出樣例
Total=3
（1）編程思路。
設f[i]表示重量i是否可以稱出。初始時，f[0]=1，其餘全部為0。輸入6種砝碼的個數w[i]，計算出所有砝碼全部使用時，可稱出的總重量tot，這也是背包的容量。
將6種砝碼按多重背包的處理方法加入背包，若重量j-w[i]*k可稱出，即f[j-w[i]*k]==1，則加上k個重w[i]的砝碼後，重量j也可以稱出，置f[j]=1。
多重背包處理完後，f[1]~f[tot]元素值為1的個數就是可稱出的不同重量的個數。
（2）源程式。
#include <stdio.h> int main() { int f[1001]={0}; int w[7]={0,1,2,3,5,10,20}; int a[7]; int i,j,k; int tot=0; // 總重量 for (i=1;i<=6;i++) { scanf("%d",&a[i]); tot+=w[i]*a[i]; } f[0]=1; for (i=1;i<=6;i++) { for (j=tot;j>=0;j--) for (k=0;k<=a[i];k++) { if (j-w[i]*k>=0 && f[j-w[i]*k]!=0) f[j]=1; } } int ans=0; for (i=1;i<=tot;i++) if (f[i]!=0) ans++; printf("Total=%d\n",ans); return 0; }
將上面的源程式提交給洛谷題庫P2347 [NOIP1996 提高組] 砝碼稱重（https://www.luogu.com.cn/problem/P2347），測評結果為“Accepted”。
【例5】買表
問題描述
Jimmy 到 Symbol 的手錶店買手錶，Jimmy 只帶了n種錢幣，第i種錢幣的面額為 ki元，張數為 ai張。Symbol 的店裡一共有m 塊手錶，第i 塊手錶的價格為 ti元。
Symbol 的手錶店不能找零，所以 Jimmy 只能在湊出恰好的錢數時才能購買一塊手錶。現在對於店裡的每塊手錶，Jimmy 想知道他能不能湊出恰好的錢數進行購買。
輸入
第一行兩個空格分隔的整數 n（1≤n≤200）和 m（1≤m≤100000） 表示錢幣數與手錶數。
接下來 n 行每行兩個空格分隔的整數 ki（1≤ki≤500000）和 ai（1≤ai≤1000）表示錢幣的面額和張數。
第 n+2行，共 m個用空格分隔的整數 ti（0≤ti≤500000），表示每塊手錶的價格。
輸出
一共m 行，對於第i 行，如果能湊出恰好的錢數購買第i 塊手錶則輸出 Yes 否則輸出 No，註意只有首字母大寫。
輸入樣例
3 5
1 2
5 1
6 3
3 19 21 1 7
輸出樣例
No
Yes
No
Yes
Yes
（1）編程思路。
設f[i]表示錢數i是否可以用n種錢幣湊出。初始時，f[0]=1，其餘全部為0。由於每種錢幣的張數較多（最多可達1000張），因此按照前面介紹的二進位數優化方法，將多重背包變化成0/1背包進行處理。
（2）源程式。
#include <stdio.h> #include <string.h> int main() { int f[500005]={0},w[2005]; int n,m; scanf("%d%d",&n,&m); int i,j; int cnt=0; for (i=1; i<=n; i++) { int k,a; scanf("%d%d",&k,&a); for (j=1; j<=a; j*=2) // 多重背包轉成0/1背包 { w[++cnt]=j*k; a-=j; } if (a>0) { w[++cnt]=k*a; } } f[0]=1; for (i=1; i<=cnt; i++) // 01背包的求解 for(j=500000; j>=w[i]; j--) if (f[j-w[i]]) f[j]=1; for (i=1;i<=m;i++) { int t; scanf("%d",&t); if (f[t]) printf("Yes\n"); else printf("No\n"); } return 0; }
將上面的源程式提交給洛谷題庫P6567 [NOI Online #3 入門組] 買表（https://www.luogu.com.cn/problem/P1776），測評結果為“Accepted”。
【例6】英雄聯盟
問題描述
正在上大學的小皮球熱愛英雄聯盟這款游戲，而且打的很菜，被網友們戲稱為「小學生」。
現在，小皮球終於受不了網友們的嘲諷，決定變強了，他變強的方法就是：買皮膚！
小皮球只會玩N個（5≤N≤150）英雄，因此，他也只准備給這N個英雄買皮膚，並且決定，以後只玩有皮膚的英雄。
這N個英雄中，第i個英雄有Ki 款皮膚，價格是每款 Ci個Q 幣（同一個英雄的皮膚價格相同）。
為了讓自己看起來高大上一些，小皮球決定給同學們展示一下自己的皮膚，展示的思路是這樣的：對於有皮膚的每一個英雄，隨便選一個皮膚給同學看。
比如，小皮球共有 5 個英雄，這 5 個英雄分別有0,0,3,2,4 款皮膚，那麼，小皮球就有3×2×4=24 種展示的策略。
現在，小皮球希望自己的展示策略能夠至少達到M （M≤1017）種，請問，小皮球至少要花多少錢呢？
輸入
第一行，兩個整數N,M。
第二行，N個整數，表示每個英雄的皮膚數量Ki。
第三行，N 個整數，表示每個英雄皮膚的價格Ci 。
輸出
一個整數，表示小皮球達到目標最少的花費。
輸入樣例
3 24
4 4 4
2 2 2
輸出樣例
18
（1）編程思路。
展示方案達到M種作為背包的容量，每一個英雄都有一個皮膚數量、一個購買的Q幣數（花費），將每個英雄的皮膚看成物品，就是有限物品數量的多重背包問題。
設f[j]表示花費j個Q幣購買英雄皮膚可得到的最大展示方案數量，則狀態轉移方程為：
f[j]=max(f[j−p∗c[i]]∗p,f[j])，其中 p是當前英雄所選的皮膚數量，c[i]該皮膚的購買價格。
多重背包處理完後，用變數i從0~tot搜索f[i]的判斷，第1次遇到的 f[i]>=m的i值就是所求的最小花費。
（2）源程式。
#include <stdio.h> long long max(long long a,long long b) { return a>b?a:b; } long long f[250000]={0}; int main() { int n; long long m; scanf("%d%lld",&n,&m); int i,j,p; int k[155],c[155]; for (i=1;i<=n;i++) scanf("%d",&k[i]); int tot=0; // 花的總錢數 for (i=1;i<=n;i++) { scanf("%d",&c[i]); tot+=c[i]*k[i]; } f[0]=1; for (i=1;i<=n;i++) { for (j=tot;j>=0;j--) for (p=0;p<=k[i];p++) { if (j-c[i]*p>=0) f[j]=max(f[j],1L*f[j-c[i]*p]*p); } } for (i=0;i<=tot;i++) if (f[i]>=m) { printf("%d\n",i); break; } return 0; }
將上面的源程式提交給洛谷題庫P5365 [SNOI2017]英雄聯盟（https://www.luogu.com.cn/problem/P5365），測評結果為“Accepted”。
【例7】寶物篩選
問題描述
小F找到了王室的寶物庫，裡面堆滿了無數價值連城的寶物。但是這裡的寶物實在是太多了，小F的採集車似乎裝不下那麼多寶物。看來小F只能含淚捨棄其中的一部分寶物了。
小F對庫里的寶物進行了整理，他發現每樣寶物都有一件或者多件。他粗略估算了下每樣寶物的價值，之後開始了寶物篩選工作：小F有一個最大載重為W的採集車，寶物庫里總共有n種寶物，每種寶物的價值為vi，重量為wi，每種寶物有mi件。小F希望在採集車不超載的前提下，選擇一些寶物裝進採集車，使得它們的價值和最大。
輸入
第一行為一個整數n（1≤n≤100）和W（0≤W≤40000），分別表示寶物種數和採集車的最大載重。
接下來n行每行三個整數vi,wi,mi。n≤∑mi ≤100000。
輸出
輸出僅一個
