背包問題（3）：完全背包
完全背包也是一種基本的背包問題模型，其基本特點是：每種物品可以放無限多次。
這個問題非常類似於0/1背包問題，所不同的是每種物品有無限件。也就是從每種物品的角度考慮，與它相關的策略已並非取或不取兩種，而是有取0件、取1件、取2件……等很多種。
完全背包問題的一般描述為：有N個物品，第i個物品的重量與價值分別為W[i]與P[i]。背包容量為V，問在每個物品有無限個（物品必須保持完整）的情況下，如何讓背包裝入的物品具有更大的價值總和。
其一般解題思路為：
令 f[i][j] 表示從編號1~i的物品中挑選任意數量的任意物品放入容量為j的背包中得到的最大價值，那麼有
f[i][j]=max { f[i−1][j]，f[i−1][j−k∗W[i]]+k∗P[i] } （0≤k && k∗W[i]≤j）
編寫程式碼時，可採用如下的循環。
for ( i=1;i<=N;i++) // 依次對每個物品進行處理
for (j=1;j<=V;j++)
for (k=1; k<=V/W[i];k++) // 物品最多只能放多少件
{
If (k*W[i]<=j)
f[i][j]=max(f[i-1][j],f[i-1][j-k*W[i]]+k*P[i]);
else
f[i][j]=f[i-1][j];
}
所求的最優值為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++) // 裝入背包的物品個數為N
for ( j=W[i];j<=V;j++) // 完全背包按由小到大順序枚舉重量
f[j]=max(f[j],f[j-W[i]]+P[i]); // 狀態轉移
所求的最優值為f[V]。
由上面的二重循環可以發現，完全背包採用的二重循環與0/1背包採用的二重循環只有內循環j的循環次序不同。
在0/1背包中內循環j要按照物品重量V~W[i]的逆序來循環。這是因為要保證第i次循環中的狀態f[i][j]是由狀態f[i-1][j-W[i]]遞推而來，從而保證每件物品只選一次。也就是要保證在考慮「選入第i件物品」時，依據的是一個絕無已經選入第i件物品的子結果f[i-1][j-W[i]]。
而完全背包的特點恰好是每種物品可選無限件，所以在考慮「加選一件第i種物品」時，正好需要一個可能已選入第i種物品的子結果f[i][j-W[i]]，所以就可以並且必須採用W[i]~V的順序循環。
【例1】買乾草
問題描述
約翰的乾草庫存已經告罄，他打算為奶牛們採購 H(1≤H≤50000) 磅乾草。
他知道N(1≤N≤100) 個乾草公司，第i公司賣的乾草包重量為Pi (1≤Pi≤5,000) 磅，需要的開銷為Ci (1≤Ci≤5,000)美元。每個乾草公司的貨源都十分充足， 可以賣出無限多的乾草包。
幫助約翰找到最小的開銷來滿足需要，即採購到至少H 磅乾草。
輸入
第1行包含兩個整數N和H
第2~N+1行，每行兩個整數，分別是Pi和Ci。
輸出
採購到至少H 磅乾草的最小開銷。
輸入樣例
2 15
3 2
5 3
輸出樣例
9
（1）編程思路。
由於要採購到至少H 磅乾草，因此背包的容量應設置為H+maxp，其中maxp為所有N個公司賣的乾草包最大重量。
定義數組int f[55005];,其中f[i]表示購買i磅乾草所需的最小花費，進行完全背包處理，求得各容量背包的最小花費。之後，循環在f[H]~f[H+maxp]中找到最小值即可。
（2）源程式。
#include <stdio.h> #include <string.h> int main() { int h,n; scanf("%d%d",&n,&h); int p[105],c[105]; int maxp=0; int i,j; for (i=1;i<=n;i++) { scanf("%d%d",&p[i],&c[i]); if (maxp<p[i]) maxp=p[i]; } int f[55005]; memset(f,0x3f,sizeof(f)); f[0]=0; for (i=1;i<=n;i++) { for (j=p[i];j<h+maxp;j++) { if (f[j]>f[j-p[i]]+c[i]) f[j]=f[j-p[i]]+c[i]; } } int res=0x7fffffff; for (i=h;i<h+maxp;i++) if (res>f[i]) res=f[i]; printf("%d\n",res); return 0; }
將上面的源程式提交給洛谷題庫P2918 [USACO08NOV]Buying Hay S（//www.luogu.com.cn/problem/P1776），測評結果為「Accepted」。
【例2】2 的次冪的和
題目描述
給出一個整數 N，將 N 分解為若干個 2 的次冪的和，共有多少種方法？
例如，當N=7時，所有合法方案如下：
1+1+1+1+1+1+1
1+1+1+1+1+2
1+1+1+2+2
1+1+1+4
1+2+2+2
1+2+4
輸入格式
輸入一個整數 N（1≤N≤106）。
輸出格式
輸出方案數對109 取模的結果。
輸入樣例
7
輸出樣例
6
（1）編程思路。
本題可以看成背包容量為n，而每個物品重量是2k 的求方案數的完全背包問題。
（2）源程式。
#include <stdio.h> int f[1000001]={0}; int main() { int i=1,j,k=0; int p[25]; while (i<1000000) { p[k++]=i; i=i*2; } int n; scanf("%d",&n); f[0]=1; for (i=0;i<k;i++) for (j=p[i];j<=n;j++) { f[j]=(f[j]+f[j-p[i]])%1000000000; } printf("%d\n",f[n]); return 0; }
將上面的源程式提交給洛谷題庫P6065 [USACO05JAN]Sumsets S（//www.luogu.com.cn/problem/P6065），測評結果為「Accepted」。
【例3】債券投資
問題描述
某銀行每年初售賣幾種債券供客戶購買投資。這幾種債券有固定的面值，並提供固定數額的年利息，在每年年底支付給所有者。債券沒有固定期限。債券有不同的大小，較大的通常會帶來更好的收益。
假設有兩種債券供投資：價值為4000元的債券，年利息為200元；價值為3000元的債券，年利息為120元。
某客戶有10000元的資本，若投資1年，他可以購買兩張4000元的債券，到期年利息為400元；也可以購買兩張3000元的債券和一張4000元的債券，到期年利息為440元。
給定一個開始的投資金額和投資年數，以及一些債券的價值和利息，求出在給定的時間段內，該金額可能會增長到多大。注意考慮購買和出售債券的最佳時間表，即每年收益獲得後，有更優的投資組合，可以賣出債券再重新購買。
輸入
輸入第一行包含一個正整數N，它是測試用例的數量。
每個測試用例的第一行包含兩個正整數：起始金額（最多1000萬元）和資本可能增長的年數（最多40年）。
下一行包含一個數字：可供投資的債券種數d（1<=d<=10）。
接下來的d行分別描述每種債券的情況，由兩個正整數組成：債券的價值和該債券的年利息。債券的價值總是1000元的倍數。債券的利息永遠不會超過其價值的10%。
輸出
對於每個測試用例，在單獨的一行上輸出————是在一個最佳的買賣時間表之後，在周期結束時的資本。
（1）編程思路。
將初始的總金額看成背包的容量，每種債券的收益作為價值，面值作為物品重量，進行完全背包處理。
由於每年收益獲得後，有更優的投資組合，可以賣出債券再重新購買。因此，對每年的投資組合均進行完全背包處理，而最初1年的背包容量為V，之後每年的背包容量均需要加上上一年的收益。
另外，由於債券的價值總是1000元的倍數，因此為了減少記憶體存儲量，將金額除以1000，以減少錢的數量。
（2）源程式。
#include <stdio.h> #include <string.h> int f[5000000]; int max(int a,int b) { return a>b?a:b; } int main() { int t; scanf("%d",&t); while (t--) { memset(f,0,sizeof(f)); int v,p; scanf("%d%d",&v,&p); int n; scanf("%d",&n); int c[20],w[20]; int i,j,k; for (i=0;i<n;i++) { scanf("%d%d",&c[i],&w[i]); c[i]/=1000; } int ans=v; for (i=0;i<p;i++) { int tmp=ans/1000; for (j=0;j<n;j++) // 完全背包 for (k=c[j];k<=tmp;k++) f[k]=max(f[k],f[k-c[j]]+w[j]); ans+=f[tmp]; } printf("%d\n",ans); } return 0; }
將上面的源程式提交給北大OJ題庫POJ 2063 Investment（//poj.org/problem?id=2063），測評結果為「Accepted」。
【例4】牛的叫聲
題目描述
農夫約翰的N（1≤N≤100）個牧場都是沿著一條筆直的道路分布的。每一個牧場可能有許多種品種的奶牛；約翰擁有B（1≤B≤20）個不同品種的奶牛，而第i種奶牛的叫聲音量為 Vi（1≤Vi≤100）。此外，有一股強風沿著道路吹來，將牛的叫聲從左往右傳遞，如果某個牧場的總音量是x，那麼它將傳遞x−1 的音量到右邊的下一個牧場。這就意味著，一個牧場里的總音量是處在該牧場的奶牛所發出的音量加上左邊前一個牧場的總音量−1 。數據保證，每一個牧場內由該牧場所有奶牛所發出的總音量最多為100000。
約翰在奶牛聚集的牧場里安裝了麥克風，這樣他能計算出從中聽到的所有牛叫聲的總音量，以便以此確定奶牛的數量。
例如，約翰擁有5個牧場，每個牧場總音量從左到右分別為為0、17、16、20、19。約翰有兩種不同品種的奶牛；第一種奶牛的叫聲音量是5，第二種奶牛的叫聲音量是7。
由此可推知，2號牧場場有2頭1號品種的奶牛，1頭2號品種奶牛；這樣2號牧場牛叫聲的總音量為（2*5+7=17），3號牧場沒有牛，前一個牧場傳遞來的總音量為16，4號牧場有1頭1號品種的奶牛，其叫聲加上傳遞過來的音量正好為20。這樣，計算出有4頭奶牛。
輸入
第1行：兩個用空格分隔的整數N和B。
第2…B+1行：第i+1行包含整數 Vi。
第B+2…B+N+1行：第 B+i+1行表示在第i個牧場內所能監聽到的總音量。
輸出
共一行，即約翰擁有的最小奶牛數量。
輸入樣例
5 2
5
7
0
17
16
20
19
輸出樣例
4
（1）編程思路。
設a[i]為第i個農場的總音量，b[i]為第i個農場的奶牛產生的音量。顯然，若a[i-1]不為0，則b[i]=a[i]-(a[i-1]-1)；否則，b[i]=a[i]。
有了每個農場奶牛產生的音量b[i]後，對每個農場進行完全背包處理，用B種物品（B種奶牛，每種奶牛的叫聲音量作為重量）以最少的數量去裝滿容量為b[i]的背包，求得每個農場的最小奶牛數量。將每個農場通過完全背包求得的最小數量累加起來就是所求的答案。
（2）源程式。
#include <stdio.h> int min(int a,int b) { return a<b?a:b; } #define INF 0x3f3f3f3f int f[100005]; int main() { int n,m; scanf("%d%d",&n,&m); int i,j,k; int a[105],b[105],v[25]; for (i=1;i<=m;i++) scanf("%d",&v[i]); a[0]=0; for (i=1;i<=n;i++) { scanf("%d",&a[i]); b[i]=a[i]; if (a[i-1]) b[i]-=(a[i-1]-1); } int ans=0; for (i=1;i<=n;i++) { for (j=0;j<=b[i];j++) f[j]=INF; f[0]=0; for (j=1;j<=m;j++) for (k=v[j];k<=b[i];k++) f[k]=min(f[k],f[k-v[j]]+1); if (f[b[i]]==INF) { ans=-1; break; } ans+=f[b[i]]; } printf("%d\n",ans); return 0; }
將上面的源程式提交給洛谷題庫P2214 [USACO14MAR]Mooo Moo S（//www.luogu.com.cn/problem/P2214），測評結果為「Accepted」。
【例5】紀念品
問題描述
小偉突然獲得一種超能力，他知道未來T天N種紀念品每天的價格。某個紀念品的價格是指購買一個該紀念品所需的金幣數量，以及賣出一個該紀念品換回的金幣數量。
每天，小偉可以進行以下兩種交易無限次：
任選一個紀念品，若手上有足夠金幣，以當日價格購買該紀念品；
賣出持有的任意一個紀念品，以當日價格換回金幣。
每天賣出紀念品換回的金幣可以立即用於購買紀念品，當日購買的紀念品也可以當日賣出換回金幣。當然，一直持有紀念品也是可以的。
T天之後，小偉的超能力消失。因此他一定會在第T天賣出所有紀念品換回金幣。
小偉現在有M枚金幣，他想要在超能力消失後擁有儘可能多的金幣。
輸入
第一行包含三個正整數 T, N, M（T≤100，N≤100，M≤1000），相鄰兩數之間以一個空格分開，分別代表未來天數T，紀念品數量N，小偉現在擁有的金幣數量M。
接下來T行，每行包含N個正整數，相鄰兩數之間以一個空格分隔。第i行的N個正整數分別為Pi,1，Pi,2，…，Pi,N ，其中Pi,j（1≤Pi,j ≤10000）表示第i天第j種紀念品的價格。
輸出
輸出僅一行，包含一個正整數，表示小偉在超能力消失後最多能擁有的金幣數量。
輸入樣例
3 3 100
10 20 15
15 17 13
15 25 16
輸出樣例
217
（1）編程思路。
T天投資，可以看成第1天買入，第2天全部賣出；第2天又賣出後又買入，第3天全部賣出；……；第T-1天賣出後又買入，第T天全部賣出。由於同一種紀念幣當天買賣價格相同，因此同一種紀念幣某天賣出又買進後相噹噹天沒有進行買賣，也就是一直持有該紀念幣。這樣，本題可採用完全背包求解，每天投資用完全背包計算收益，共進行T-1天完全背包。
每天完全背包時，將當天手裡的金幣數當做背包的容量（初始時為M，之後每天結束後將當天的收益加到M上，作為下一天的背包容量），把紀念品當天的價格當成它的重量，把紀念品下一天的價格與當天的價格的差值當做它的價值。
設f[i]為用i個金幣去購買紀念品所能盈利的最大值（不含成本），則有
f[j]=max(f[j],f[j−price[i][k]]+price[i][k+1]−price[i][k]); （k代表第k天）
（2）源程式。
#include <stdio.h> #include <string.h> int max(int a,int b) { return a>b?a:b; } int main() { int t,n,m; scanf("%d%d%d",&t,&n,&m); int p[101][101], f[10001]; int i,j; for (i=1; i<=t; i++) for (j=1; j<=n; j++) scanf("%d",&p[j][i]); int k; for (k=1; k<t; k++) { memset(f, 0, sizeof f); for (i=1; i<=n; i++) for (j=p[i][k]; j<=m; j++) // 完全背包 f[j] = max(f[j], f[j-p[i][k]] + p[i][k+1]-p[i][k]); m += f[m]; } printf("%d\n",m); return 0; }
將上面的源程式提交給洛谷題庫P5662 [CSP-J2019] 紀念品（//www.luogu.com.cn/problem/P5662），測評結果為「Accepted」。
【例6】乳酪塔
問題描述
FJ要建一個乳酪塔，高度最大為T（1 <= T <= 1,000）。他有N（1 <= N <= 100）種乳酪。第i種乳酪的高度為Hi（一定是5的倍數），價值為Vi。一塊高度Hi>=K的乳酪被稱為大乳酪，一個乳酪如果在它上方有大乳酪（如果有多塊就只算一次），它的高度Hi就會變成原來的4/5。FJ想讓他的乳酪塔價值和最大。請你求出這個最大值。
輸入
第一行三個數N,T,K，意義如上所述。
接下來n行，每行兩個數Vi，hi。
輸出
乳酪塔的最大價值
輸入樣例
3 53 25
100 25
20 5
40 10
輸出樣例
240
（1）編程思路。
如果沒有大乳酪，這個題目可以用完全背包模板來做。但是加上了大乳酪，因為被大乳酪壓著的乳酪高度會變成原來的4/5，所以需要把有大乳酪和沒有大乳酪分開來看。
定義數組int f[1010][2]={0};，其中f[i][0]表示沒有大乳酪時高度為i的乳酪塔的最大價值和；f[i][1]表示有大乳酪時高度為i的乳酪塔的最大價值和
如果沒有大乳酪，則 f[j][0]=max(f[j][0],f[j-h[i]][0]+v[i]);
如果枚舉到的某個乳酪正好是大乳酪，則f[j][1]=max(f[j][1],f[(j-w[i])*4/5][0]+v[i]);
如果某個乳酪上能放大乳酪，也就是f[j-w[i]*4/5][1]存在解，則f[j][1]=max(f[j][1],f[j-w[i]*4/5][1]+v[i]);
另外，需要將乳酪按其高度先從大到小排序，這樣先枚舉大乳酪，再枚舉小乳酪；再將全部的大乳酪按高度從小到大排列。
（2）源程式。
#include <stdio.h> struct Node { int v,h; }; int max(int a,int b) { return a>b?a:b; } int main() { int n,T,k; scanf("%d%d%d",&n,&T,&k); struct Node a[105],temp; int i,j; int cnt=0; for (i=1;i<=n;i++) { scanf("%d%d",&a[i].v,&a[i].h); if(a[i].h>=k) cnt++; } for (i=1;i<n;i++) // 將乳酪按高度從大到小排序 for (j=1;j<=n-i;j++) if (a[j].h<a[j+1].h) { temp=a[j]; a[j]=a[j+1]; a[j+1]=temp; } for (i=1;i<cnt;i++) // 將大乳酪再按高度從小到大排序 for (j=1;j<=cnt-i;j++) if (a[j].h>a[j+1].h) { temp=a[j]; a[j]=a[j+1]; a[j+1]=temp; } int f[1010][2]={0}; for (i=1;i<=T;i++) f[i][1]=-1; for (i=1;i<=n;i++) for (j=a[i].h;j<=T;j++) { f[j][0]=max(f[j][0],f[j-a[i].h][0]+a[i].v); if (f[j-a[i].h*4/5][1]!=-1) f[j][1]=max(f[j][1],f[j-a[i].h*4/5][1]+a[i].v); if (a[i].h>=k) f[j][1]=max(f[j][1],f[(j-a[i].h)*4/5][0]+a[i].v); } printf("%d\n",max(f[T][0],f[T][1])); return 0; }
將上面的源程式提交給洛谷題P2979 [USACO10JAN]Cheese Towers S（//www.luogu.com.cn/problem/P2979），測評結果為「Accepted」。
【例7】股票市場
問題描述
儘管奶牛天生謹慎，它們仍然在住房抵押信貸市場中大受打擊，現在它們準備在股市上碰碰運氣。貝西有內部消息，她知道S 只股票在今後 D 天內的價格。
假設在一開始，她籌集了 M 元錢，那麼她該怎樣操作才能賺到最多的錢呢？貝西在每天可以買賣多隻股票，也可以多次買賣同一隻股票，交易單位必須是整數，數量不限。舉一個牛市的例子：
假設貝西有 10 元本金，股票價格如下：
最賺錢的做法是：今天買入 A 股 1 張，到明天把它賣掉並且買入 B 股 1 張，在後天賣掉 B股，這樣貝西就有 24 元了。
輸入
第一行：三個整數 S， D 和 M（2≤S≤50 ，2≤D≤10 ，1≤M≤200000）。
第二行到第 S + 1 行：第 i + 1 行有 D 個整數，表示第 i 種股票在第一天到最後一天的售價。
輸出
單個整數：表示奶牛可以獲得的最大錢數，保證這個數不會超過 500000。
輸入樣例
2 3 10
10 15 15
13 11 20
輸出樣例
24
（1）編程思路。
D天的股票投資，可以看成第1天買入，第2天全部賣出；第2天又賣出後又買入，第3天全部賣出；……；第D-1天賣出後又買入，第D天全部賣出。由於同一種股票當天的交易價格相同，因此同一種股票某天賣出又買入，相噹噹天沒有進行交易，也就是一直持有該股票。這樣，本題可採用完全背包求解，每天投資用完全背包計算收益，從第2天到第D天共進行D-1天完全背包。
每天完全背包時，將當天手裡的可投資金額數當做背包的容量（初始時為M，之後每天結束後將當天的收益加到M上，作為下一天的背包容量），把股票前一天的交易價格當成它的重量（前一天買入的），把股票當天的交易價格與前一天的交易價格的差值當做它的價值。
設f[i]保存投資i元時獲得的最大收益。
狀態轉移方程為 f[i]=max{f[i],f[i-a[j][k-1]]+a[j][k]-a[j][k-1]}
（2）源程式。
#include <stdio.h> #include <string.h> int max(int a,int b) { return a>b?a:b; } int f[500001]; int main() { int s,d,m; scanf("%d%d%d",&s,&d,&m); int a[51][11]; int i,j; for (i=1;i<=s;i++) for (j=1;j<=d;j++) scanf("%d",&a[i][j]); for (int k=2;k<=d;k++) { memset(f,0,sizeof(f)); int maxx=0; for (i=1;i<=s;i++) { for (j=a[i][k-1];j<=m;j++) { f[j]=max(f[j],f[j-a[i][k-1]]+a[i][k]-a[i][k-1]); maxx=max(f[j],maxx); } } m+=maxx; } printf("%d\n",m); return 0; }
將上面的源程式提交給洛谷題P2938 [USACO09FEB]Stock Market G（//www.luogu.com.cn/problem/P2938），測評結果為「Accepted」。
練習題
1．P1474 [USACO2.3]Money System（//www.luogu.com.cn/problem/P1474）
#include <stdio.h> int main() { int v,n; scanf("%d%d",&v,&n); long long f[10001]={0}; int a[26]; int i,j; for (i=0;i<v;i++) scanf("%d",&a[i]); f[0]=1; for (i=0;i<v;i++) for (j=a[i];j<=n;j++) f[j]+=f[j-a[i]]; printf("%lld\n",f[n]); return 0; }
View Code
2．P1616 瘋狂的採藥（//www.luogu.com.cn/problem/P1616）
#include <stdio.h> long long f[10000001]={0}; int main() { int t,m; scanf("%d%d",&t,&m); int a[10001],b[10001]; int i,j; for (i=1;i<=m;i++) scanf("%d%d",&a[i],&b[i]); for (i=1;i<=m;i++) for (j=a[i];j<=t;j++) { if (f[j]<f[j-a[i]]+b[i]) f[j]=f[j-a[i]]+b[i]; } printf("%lld\n",f[t]); return 0; }
View Code
3．P1679 神奇的四次方數（//www.luogu.com.cn/problem/P1679）
#include <stdio.h> #include <math.h> int main() { int p[20]={1}; int i,j; for (i=1;i<=18;i++) p[i]=i*i*i*i; int m; scanf("%d",&m); int n=(int)sqrt(sqrt(1.0*m)); int f[105001]; f[0]=0; for (i=1;i<=m;i++) f[i]=1<<30; for (i=1;i<=n;i++) for (j=p[i];j<=m;j++) if (f[j]>f[j-p[i]]+1) f[j]=f[j-p[i]]+1; printf("%d\n",f[m]); return 0; }
View Code
4．P2722 [USACO3.1]總分 Score Inflation（//www.luogu.com.cn/problem/P2722）
#include <stdio.h> int main() { int m,n; scanf("%d%d",&m,&n); int p[10001],t[10001],f[10001]={0}; int i,j; for (i=1;i<=n;i++) scanf("%d%d",&p[i],&t[i]); for (i=1;i<=n;i++) for (j=t[i];j<=m;j++) { if (f[j]<f[j-t[i]]+p[i]) f[j]=f[j-t[i]]+p[i]; } printf("%d\n",f[m]); return 0; }
View Code
5．P2737 [USACO4.1]麥香牛塊（//www.luogu.com.cn/problem/P2737）
#include <stdio.h> #define MAXNUM 65636 int main() { int opt[MAXNUM+5]={0}; int n; scanf("%d",&n); int i,j; opt[0]=1; for (i=1;i<=n;i++) { int v; scanf("%d",&v); for (j=v;j<=MAXNUM;j++) { if (opt[j-v]==1) opt[j]=1; } } for (i=MAXNUM;i>=1;i--) if (opt[i]==0) break; if (i>65536) printf("0\n"); else printf("%d\n",i); return 0; }
View Code
6．POJ1252 Euro Efficiency（//poj.org/problem?id=1252）
#include <stdio.h> #include <string.h> int min(int a,int b) { return a<b?a:b; } int main() { int t; scanf("%d", &t); while (t--) { int value[6]; int i,j; for (i=0; i<6; i++) scanf("%d", &value[i]); int f[2101]; memset(f, 0x7f7f7f7f, sizeof(f)); f[0] = 0; for (i=0; i<6; i++) for (j=value[i]; j<=2000; j++) f[j] = min(f[j], f[j-value[i]] + 1); for (i=0; i<6; i++) for (j=2000; j>=0; j--) f[j] = min(f[j], f[j+value[i]] + 1); int max = 0, sum = 0; for (i=1; i<=100; i++) { sum += f[i]; if (f[i] > max) max = f[i]; } printf("%.2f %d\n", sum/100.0, max); } return 0; }
View Code
7．POJ1384 Piggy-Bank （//poj.org/problem?id=1384）
#include <stdio.h> #include <string.h> int min(int a,int b) { if (a<b) return a; else return b; } int main() { int p[501],w[501],f[10050]; int t; scanf("%d",&t); while (t--) { int a,b; scanf("%d%d",&a,&b); int lim=b-a; int n; scanf("%d",&n); int i,j; for (i=0;i<n;i++) { scanf("%d%d",&p[i],&w[i]); } for (i=0;i<=lim;i++) { f[i]=100000000; } f[0]=0; for (i=0;i<n;i++) { for (j=w[i];j<=lim;j++) { f[j]=min(f[j],f[j-w[i]]+p[i]); } } if (f[lim]==100000000) printf("This is impossible.\n"); else printf("The minimum amount of money in the piggy-bank is %d.\n",f[lim]); } return 0; }
View Code
8．POJ1882 Stamps（//poj.org/problem?id=1882）
#include <stdio.h> #define INF 99999999 int min(int a,int b) { return a<b?a:b; } int main() { int f[1001]; // f[j]表示構成價值j的郵票所需最小的郵票數 int d[10]; int a[10][10]; int s; while (scanf("%d",&s) && s != 0) { int n; scanf("%d",&n); int ans = 0,index = 0; int i,j,k; for (i=0; i<n; i++) { scanf("%d",&d[i]); for (j=0; j<d[i]; j++) scanf("%d",&a[i][j]); int maxV = a[i][d[i] - 1] * s; // 最多可貼的總面額=最大面額*張數 for (j = 0; j<=maxV; j++) f[j] = INF; f[0] = 0; for (j=0; j<d[i]; j++) // 完全背包 { for (k=a[i][j]; k<=maxV; k++) { f[k] = min(f[k], f[k-a[i][j]]+1); } } for (j=0; j<=maxV; j++) if (f[j] > s) break; j--; if (j>ans) { ans = j; index = i; } else if (j== ans) { if (d[i]<d[index]) { ans = j; index = i; } else if (d[i]==d[index] && a[i][d[i]-1]<a[index][d[index]-1]) { ans = j; index = i; } } } printf("max coverage = %d :",ans); for (i=0; i<d[index]; i++) printf(" %d",a[index][i]); printf("\n"); } return 0; }
View Code
