本篇是根據 GopherCon SG 2019 “Understanding Allocations” 演講的學習筆記。 Understanding Allocations: the Stack and the Heap - GopherCon SG 2019 - YouTube 理解分配：棧和堆 ...
混合背包就是將前面三種基本的背包問題疊加成較複雜的問題。也就是說，有的物品只可以取一次（0/1背包），有的物品可以取無限次（完全背包），有的物品可以取的次數有一個上限（多重背包）。
0/1背包與完全背包的混合比較簡單。如果只有兩類物品：一類物品只能取一次，另一類物品可以取無限次，那麼只需在對每個物品應用轉移方程時，根據物品的類別選用逆序（0/1背包）或順序（完全背包）的迴圈即可。
一般可以編寫如下的迴圈。
for (i=1;i<=N;i++) // 裝入背包的物品個數為N
{
if (第i件物品只能取1次) // 0/1背包
for (j=V;j>=W[i];j--) // 0/1背包按由大到小順序枚舉重量
f[j]=max(f[j],f[j-W[i]]+P[i]);
else // 第i件物品可以取無數次，完全背包
for ( j=W[i];j<=V;j++) // 完全背包按由小到大順序枚舉重量
f[j]=max(f[j],f[j-W[i]]+P[i]);
}
如果再加上多重背包，一般可以編寫如下迴圈程式。
for (i=1;i<=N;i++) // 裝入背包的物品個數為N
{
if (第i件物品只能取1次) // 0/1背包
{
for (j=V;j>=W[i];j--)
f[j]=max(f[j],f[j-W[i]]+P[i]);
}
else if (第i件物品可以取無數次) // 完全背包
{
for ( j=W[i];j<=V;j++)
f[j]=max(f[j],f[j-W[i]]+P[i]);
}
else if (第i件物品可以取c[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]);
}
}
【例1】最多的糖果數
問題描述
今天是CRB的生日。他媽媽決定給她可愛的兒子買很多禮物。
她帶著M元（貨幣單位）去了最近的商店。
商店裡有N種禮物。買一件第i種禮物要花Wi元。
但由於商店的老闆是她的朋友，如果她買了x（x>0）件第i種禮物，花費x×Wi元，老闆會送給她Ai×x+Bi顆糖果。
她想得到最多的糖果。你的任務是幫助她。
輸入
有多個測試用例。輸入的第一行包含一個整數T（1≤ T≤ 20），表示測試用例的數量。
對於每個測試用例：第一行包含兩個整數M（1≤ M≤ 2000）和N（1≤ N≤ 1000）。接下來是N行，第i行包含三個空格分隔的整數Wi（1≤Wi≤2000）、Ai和Bi（0≤Ai，Bi≤2000）。
輸出
對於每個測試用例，輸出她能獲得的最大糖果。
輸入樣例
1
100 2
10 2 1
20 1 1
輸出樣例
21
（1）編程思路。
對於第i件商品，如果只買1個，得到的價值是Ai+Bi；如果在買1個的基礎上再買，得到的價值就是Ai。也就是說，第i件商品，除了第一次得到Ai+Bi顆糖果，以後購買都只得到Ai顆糖果，這樣可以將第i件商品看成兩種商品，其中兩種商品的購買代價都是Wi，第一種的價值是Ai+Bi，但是只允許買一次；第二種的價值是Ai，可以無限次購買。第一種商品用0/1背包處理，第二種商品用完全背包處理，並且先進行0/1背包，再進行完全背包。由於第一種商品的價值Ai+Bi大於或等於第二種商品的價值，付出相同的代價，價值大的肯定會被先考慮，也就是在用完全背包處理第二種商品時，第一種商品肯定已經被添加到背包里了。
（2）源程式。
#include <stdio.h> #include <string.h> int max(int a,int b) { return a>b?a:b; } int main() { int f[2005]; int t; scanf("%d", &t); while (t--) { int m,n; scanf("%d%d", &m, &n); memset(f,0,sizeof(f)); int w, a, b; int i,j; for (i = 1; i <=n; i++) { scanf("%d%d%d", &w, &a, &b); for (j= m; j >= w; j--) // 每個商品的第1件只買1次，0/1背包 f[j] = max(f[j], f[j-w] + a + b); for (j = w; j<=m; j++) // 每個商品之後可購買次數不限，完全背包 f[j] = max(f[j], f[j-w] + a); } int ans = 0; for (i=0; i<=m; i++) ans = max(ans, f[i]); printf("%d\n", ans); } return 0; }
將上面的源程式提交給HDU題庫HDU 5410 CRB and His Birthday（http://acm.hdu.edu.cn/showproblem.php?pid=5410），測評結果為“Accepted”。
【例2】櫻花
題目描述
愛與愁大神後院里種了n棵櫻花樹，每棵都有美學值 Ci (0≤Ci≤200)。愛與愁大神在每天上學前都會來賞花。愛與愁大神可是生物學霸，他懂得如何欣賞櫻花：一種櫻花樹看一遍過，一種櫻花樹最多看 Ai (0≤Ai≤100)遍，一種櫻花樹可以看無數遍。但是看每棵櫻花樹都有一定的時間Ti (0≤Ti≤100)。愛與愁大神離去上學的時間只剩下一小會兒了。求解看哪幾棵櫻花樹能使美學值最高且愛與愁大神能準時（或提早）去上學。
輸入
共 n+1行：
第1行：現在時間 Ts（幾時：幾分），去上學的時間 Te（幾時：幾分），愛與愁大神院子里有幾棵櫻花樹 n。這裡的Ts，Te格式為：hh:mm，其中0≤hh≤23，0≤mm≤59，且 hh,mm,n均為正整數。開始時間距離結束時間不超過 1000分鐘，n≤10000。
第2行到第n+1 行，每行三個正整數：看完第i棵樹的耗費時間Ti，第i棵樹的美學值Ci，看第i棵樹的次數Pi（Pi =0 表示無數次，Pi是其他數字表示最多可看的次數Pi）。
輸出
只有一個整數，表示最大美學值。
輸入樣例
6:50 7:00 3
2 1 0
3 3 1
4 5 4
輸出樣例
11
樣例解釋
賞第一棵櫻花樹一次，賞第三棵櫻花樹2次。
（1）編程思路1。
一種櫻花樹看一遍過（0/1背包），一種櫻花樹最多看 Ai (0≤Ai≤100)遍（多重背包），一種櫻花樹可以看無數遍（完全背包）。
設現在時間為h1：m1，去上學的時間為h2：m2，則limt=h2*60+m2-(h1*60+m1)就是背包的容量，將看櫻花耗費的時間ti看成物品的重量，櫻花的美學值看成物品的價值，按上面的介紹，3種背包混合時分別處理即可。
（2）源程式1。
#include <stdio.h> #include <string.h> int max(int a,int b) { return a>b?a:b; } int main() { int n,h1,m1,h2,m2; scanf("%d:%d %d:%d %d",&h1,&m1,&h2,&m2,&n); int limt=h2*60+m2-(h1*60+m1); int f[1005]={0}; int i,j,k; for (i=1;i<=n;i++) { int t,c,p; scanf("%d%d%d",&t,&c,&p); if (p==1) // 看一次，0/1背包 { for (j=limt;j>=t;j--) f[j]=max(f[j],f[j-t]+c); } else if (p==0) // 看無數次，完全背包 { for (j=t;j<=limt;j++) f[j]=max(f[j],f[j-t]+c); } else // 看pi次，多重背包 { for (j=limt; j>=0; j--) for (k=0; k<=p && k*t <=j; k++) f[j] = max( f[j], f[j-k*t] + k *c); } } printf("%d\n",f[limt]); return 0; }
（3）編程思路2。
可以將完全背包和多重背包均轉化為0/1背包求解。櫻花可以看無數遍，實際上由於背包容量的限制，最多也只能看limt/t遍，因此完全背包可看成一個物品取limt/t的多重背包，採用二進位拆分優化的方法將多重背包轉換為0/1背包統一求解。
（4）源程式2。
#include <stdio.h> #include <string.h> int t[1000005],c[1000005]; int main() { int n,h1,m1,h2,m2; scanf("%d:%d %d:%d %d",&h1,&m1,&h2,&m2,&n); int limt=h2*60+m2-(h1*60+m1); int i,j; int cnt=0; for (i=1;i<=n;i++) { int a,b,p; scanf("%d%d%d",&a,&b,&p); if (p==0) p=p=limt/a; for (j=1;j<=p;j<<=1) { t[++cnt]=j*a; c[cnt]=j*b; p-=j; } if (p) { t[++cnt]=a*p; c[cnt]=b*p; } } int f[1005]; memset(f,0,sizeof(f)); for (i=1;i<=cnt;i++) for (j=limt;j>=t[i];j--) if (f[j]<f[j-t[i]]+c[i]) f[j]=f[j-t[i]]+c[i]; printf("%d\n",f[limt]); return 0; }
將上面的源程式提交給洛谷題庫P1833 櫻花（https://www.luogu.com.cn/problem/P1833），測評結果為“Accepted”。
練習題
1．P1782 旅行商的背包（https://www.luogu.com.cn/problem/P1782）
#include <stdio.h> long long max(long long a,long long b) { return a>b?a:b; } int main() { long long n,m,C; scanf("%lld%lld%lld",&n,&m,&C); long long f[10005]={0}; long long i,j,k; for (i=1;i<=n;i++) // n種物品多重背包 { long long v,w,d; scanf("%lld%lld%lld",&v,&w,&d); if (v*d>=C) { for (j=v;j<=C;j++) f[j]=max(f[j],f[j-v]+w); } else { k=1; while (k<d) { for (j=C;j>=k*v;j--) f[j]=max(f[j],f[j-k*v]+k*w); d-=k; k*=2; } if (d>0) { for (j=C;j>=d*v;j--) f[j]=max(f[j],f[j-d*v]+d*w); } } } for (i=1;i<=m;i++) // m件奇貨是0/1背包 { long long a,b,c; scanf("%lld%lld%lld",&a,&b,&c); for (j=C;j>=0;j--) for (k=0;k<=j;k++) f[j]=max(f[j],f[j-k]+(a*k+b)*k+c); } printf("%lld\n",f[C]); return 0; }View Code
2．P2851 [USACO06DEC]The Fewest Coins G（https://www.luogu.com.cn/problem/P2851）
#include <stdio.h> #include <string.h> #define INF 0x3f3f3f3f int min(int a,int b) { return a<b?a:b; } int main() { int f1[25000]; // 約翰對不同金額所付的最少硬幣數量 int f2[25000]; // 店家對不同金額找零的最少硬幣數量 int n,t; scanf("%d%d",&n,&t); int sum=0; int i,j; int c[105],v[105]; for (i=0;i<n;i++) { scanf("%d",&v[i]); if (sum<v[i]) sum=v[i]; } for (i=0;i<n;i++) scanf("%d",&c[i]); sum=sum*sum+t+1; memset(f1,INF,sizeof(f1)); memset(f2,INF,sizeof(f2)); f1[0]=0; f2[0]=0; for (i=0;i<n;i++) { for (j=v[i];j<=sum;j++) // 店家找零是完全背包 { f2[j]=min(f2[j],f2[j-v[i]]+1); } if (c[i]*v[i]>=sum) // 約翰付賬是多重背包 { for (j=v[i];j<=sum;j++) f1[j]=min(f1[j],f1[j-v[i]]+1); } else { int k=1; int temp=c[i]; while (k<temp) { for (j=sum;j>=k*v[i];j--) f1[j]=min(f1[j],f1[j-k*v[i]]+k); temp-=k; k*=2; } for (j=sum;j>=temp*v[i];j--) f1[j]=min(f1[j],f1[j-temp*v[i]]+temp); } } int res=INF; for (i=t;i<=sum;i++) { res=min(res,f1[i]+f2[i-t]); } if (res==INF) printf("-1\n"); else printf("%d\n",res); return 0; }View Code
