記得去年的校圣誕編程大賽的初賽和復(fù)賽中有3，4道類型相似的題目，當(dāng)時對于剛加入ACMER行列的我并不了解這是哪一類的題目，只覺得這些題目有一定的規(guī)律。后來寫的程序多了，接觸的算法也多了，慢慢的知道那3，4道題目其實(shí)是動態(tài)規(guī)劃下的”背包問題”.現(xiàn)在基本上了解了這類題目的解題思路和應(yīng)對方法,故想借此對各種背包問題做一個詳細(xì)的解釋.
0-1背包
0-1背包是基礎(chǔ),接下來所有背包的問題都會圍繞0-1背包展開,所以我將會特別仔細(xì)的進(jìn)行闡釋.當(dāng)然0-1背包可以用貪心來完成,考慮到各種背包的通用性,貪心解法我就略過了,直接從動態(tài)規(guī)劃的解法開始講起.
先從一道例題講起:
0-1原型:
一個旅行者有一個最多能用M公斤的背包，現(xiàn)在有N件物品，
它們的重量分別是W1，W2，...,Wn,
它們的價(jià)值分別為P1,P2,...,Pn.
問:每種物品只有一件，則旅行者能獲得的最大總價(jià)值是多少?
解答:
其實(shí)很多人都能從網(wǎng)上搜到0-1背包的狀態(tài)轉(zhuǎn)移方程,即: f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]}.但是對它的靈活運(yùn)用和具體實(shí)現(xiàn)不甚了解，接下來我以這題為例展示此狀態(tài)方程的由來，以便接下來后面幾種背包的學(xué)習(xí).
因?yàn)楸嘲畲笕萘?/span>M未知。所以，我們的程序要從1到M一個一個的試。比如，開始任選N件物品的一個。看對應(yīng)M的背包，能不能放進(jìn)去，如果能放進(jìn)去，并且還有多的空間，則，多出來的空間里能放N-1物品中的最大價(jià)值。怎么能保證總選擇是最大價(jià)值呢？
看下表。
測試數(shù)據(jù)：
10,3
3,4
4,5
5,6
c[i][j]數(shù)組保存了1,2,3號物品依次選擇后的最大價(jià)值.
這個最大價(jià)值是怎么得來的呢?從背包容量為0開始,1號物品先試,0,1,2,的容量都不能放.所以置0,背包容量為3則里面放4.這樣,這一排背包容量為4,5,6,....10的時候，最佳方案都是放4.假如1號物品放入背包.則再看2號物品.當(dāng)背包容量為3的時候，最佳方案還是上一排的最價(jià)方案c為4.而背包容量為5的時候，則最佳方案為自己的重量5.背包容量為7的時候，很顯然是5加上一個值了。加誰??很顯然是7-4=3的時候.上一排 c3的最佳方案是4.所以。總的最佳方案是5+4為9.這樣.一排一排推下去。最右下放的數(shù)據(jù)就是最大的價(jià)值了。(注意第3排的背包容量為7的時候,最佳方案不是本身的6.而是上一排的9.說明這時候3號物品沒有被選.選的是1,2號物品.所以得9.)
從以上最大價(jià)值的構(gòu)造過程中可以看出。
f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]} 這就是0-1背包的狀態(tài)轉(zhuǎn)移方程了
/以下是實(shí)際程序，此程序來源自網(wǎng)絡(luò)
1
/-----------------------------------------------------------------------------------/
2#include<stdio.h>
3
int c[10][100];/**//*對應(yīng)每種情況的最大價(jià)值*/
4int knapsack(int m,int n)
5
{
6
int i,j,w[10],p[10];
7 for(i=1;i<n+1;i++)
8 scanf("\n%d,%d",&w[i],&p[i]);
9 for(i=0;i<10;i++)
10 for(j=0;j<100;j++)
11
c[i][j]=0;/**//*初始化數(shù)組*/
12 for(i=1;i<n+1;i++)
13 for(j=1;j<m+1;j++)
14 {
15 if(w[i]<=j) /**//*如果當(dāng)前物品的容量小于背包容量*/
16 {
17 if(p[i]+c[i-1][j-w[i]]>c[i-1][j])
18 /**//*如果本物品的價(jià)值加上背包剩下的空間能放的物品的價(jià)值*/
19 /**//*大于上一次選擇的最佳方案則更新c[i][j]*/
20 c[i][j]=p[i]+c[i-1][j-w[i]];
21 else
22 c[i][j]=c[i-1][j];
23
}
24 else c[i][j]=c[i-1][j];
25 }
26 return(c[n][m]);
27
28
}
29int main()
30{
31 int m,n;int i,j;
32 scanf("%d,%d",&m,&n);
33 printf("Input each one:\n");
34 printf("%d",knapsack(m,n));
35 printf("\n");/**//*下面是測試這個數(shù)組,可刪除*/
36 for(i=0;i<10;i++)
37 for(j=0;j<15;j++)
38 {
39 printf("%d ",c[i][j]);
40 if(j==14)printf("\n");
41 }
42 system("pause");
43}
44
45/--------------------------------------------------------------------------------------------------------------------/
46/--------------------------------------------------------------------------------------------------------------------/
47
好了繼續(xù)，看完上面的解釋，相信你對0-1背包的運(yùn)作有了基本的了解，下面就來練練手吧.
Bone Collector
Time Limit : 2000/1000ms (Java/Other) Memory Limit : 32768/32768K (Java/Other)
Total Submission(s) : 125 Accepted Submission(s) : 37
Font: Times New Roman | Verdana | Georgia
Font Size: ← →
Problem Description
Many years ago , in Teddy’s hometown there was a man who was called “Bone Collector”. This man like to collect varies of bones , such as dog’s , cow’s , also he went to the grave …
The bone collector had a big bag with a volume of V ,and along his trip of collecting there are a lot of bones , obviously , different bone has different value and different volume, now given the each bone’s value along his trip , can you calculate out the maximum of the total value the bone collector can get ?
Input
The first line contain a integer T , the number of cases.
Followed by T cases , each case three lines , the first line contain two integer N , V, (N <= 1000 , V <= 1000 )representing the number of bones and the volume of his bag. And the second line contain N integers representing the value of each bone. The third line contain N integers representing the volume of each bone.
Output
One integer per line representing the maximum of the total value (this number will be less than 231).
Sample Input
1
5 10
1 2 3 4 5
5 4 3 2 1
Sample Output
14
這是杭電ACM oj 上的題目，是不是和剛才的題目很相似，那就開始動手吧。
寫完可以在http://acm.hdu.edu.cn/diy/contest_showproblem.php?pid=1001&cid=1922上提交試試;
僅供參考的ac程序:
1/**//*
2copyright jj
3hdu-1922
4 2008.12.30
5 狀態(tài):已AC
6*/
7#include<iostream>
8using namespace std;
9int max(int a,int b){
10 int temp;
11 if(a>b) temp=a;
12 else temp=b;
13 return temp;
14}
15int zeroonepack(int n,int m,int v[],int w[],int *maj) //0-1背包部分代碼
16{
17 for(int y=0;y<=m;y++) //初始化行為0
18 maj[y]=0;
19
20 for(int i=1;i<=n;i++) //注意循環(huán)的始末
21 for(int j=m;j>=0;j--) //注意此處
22 if(w[i]<=j)
23 maj[j]=max(maj[j],maj[j-w[i]]+v[i]); //最關(guān)鍵的狀態(tài)轉(zhuǎn)移方程
24 else
25 maj[j]=maj[j];
26 return maj[m]; //返回最后一行最后一個值
27}
28int main()
29{
30 int times,n,m,*maj;
31 cin>>times;
32 for(int e=0;e<times;e++)
33 {
34 cin>>n>>m;
35 int *w=new int[n+1];
36 for(int r=1;r<=n;r++)
37 cin>>w[r];
38 int *v=new int[n+1];
39 for(int k=1;k<=n;k++)
40 cin>>v[k];
41 maj=new int[m+1];
42
43cout<< zeroonepack(n,m,w,v,maj)<<endl;;
44}
45 return 0;
46}
47
48
49/--------------------------------------------------------------------------------------------------------------------/
50/--------------------------------------------------------------------------------------------------------------------/
51
如果不懂上述代碼,請?jiān)倩乜磮D片,接下來我們再來看一道題目
擎天柱
Time Limit:1000MS Memory Limit:32768K
Description:
話說月光家里有許多玩具，最近他又看上了DK新買的“擎天柱”，就想用自己的跟DK的換。每種玩具都有特定的價(jià)格，價(jià)格為整數(shù)。只有月光拿出的玩具的總價(jià)格與“擎天柱”的價(jià)格相等才能換得“擎天柱”。同時，月光還希望能用最少的玩具數(shù)換回“擎天柱”。請問，月光能順利得到夢寐以求的“擎天柱”嗎？
Input:
輸入數(shù)據(jù)包含多組；對于每組數(shù)據(jù)，第一行為一個正整數(shù)n(1 ≤n≤10); 表示月光手頭有n個玩具。接下來一行有n個正整數(shù)P1，P2，……，Pn（1 ≤ Pi ≤ 1000），Pi為第i個玩具的所對應(yīng)的價(jià)格。最后一行為一個正整數(shù)m(1 ≤ m ≤10000)，為“擎天柱”的價(jià)格。
Output:
對于每組數(shù)據(jù)，如果能換得“擎天柱”則輸出最少玩具數(shù)；否則，輸出“-1”。
Sample Input:
3
1 2 3
4
4
4 3 3 5
2
Sample Output:
2
-1
Source:
這是浙工大ACM上的題目做完可以提交試試
url: http://acm.zjut.edu.cn/ShowProblem.aspx?ShowID=1355
祝你好運(yùn)！~
想用剛才的方法做？發(fā)現(xiàn)題目里多了什么條件沒？
對了！那就是“只有月光拿出的玩具的總價(jià)格與“擎天柱”的價(jià)格相等才能換得“擎天柱””這句。 換句話說題目要求的不僅僅是最優(yōu)值而且要求你求的是“能把包裝滿”的最優(yōu)值！！！
怎么辦？難道就這樣束手無策了么？
解答:
0-1背包也是背包問題的最常見的兩種問法:
一是要求“恰好裝滿背包”時的最優(yōu)解
二是“沒有要求必須把背包裝滿”。
這兩種問法的實(shí)現(xiàn)方法不同點(diǎn)主要在初始化上。
如果是第一種問法，要求恰好裝滿背包，那么在初始化時除了f[0]為0其它f[1..V]均設(shè)為-∞，這樣就可以保證最終得到的f[N]是一種恰好裝滿背包的最優(yōu)解。
如果并沒有要求必須把背包裝滿，而是只希望價(jià)格盡量大，初始化時應(yīng)該將f[0..V]全部設(shè)為0。
為什么呢？
可以這樣理解：初始化的f數(shù)組事實(shí)上就是在沒有任何物品可以放入背包時的合法狀態(tài)。如果要求背包恰好裝滿，那么此時只有容量為0的背包可能被價(jià)值為0的nothing“恰好裝滿”，其它容量的背包均沒有合法的解，屬于未定義的狀態(tài)，它們的值就都應(yīng)該是-∞了。如果背包并非必須被裝滿，那么任何容量的背包都有一個合法解“什么都不裝”，這個解的價(jià)值為0，所以初始時狀態(tài)的值也就全部為0了。
這個小技巧完全可以推廣到其它類型的背包問題，后面也就不再對進(jìn)行狀態(tài)轉(zhuǎn)移之前的初始化進(jìn)行講解
再來看看我AC的代碼:
1/**//*
2copyright jj
3zjut-1355
4 2009.01.03
5 狀態(tài):已AC
6*/
7#include<iostream>
8#include<stdlib.h>
9using namespace std;
10int n,sum;
11int min(int a,int b){
12 int temp;
13 if(a>b) temp=b;
14 else temp=a;
15 return temp;
16}
17
18int zeroonepack(int a[],int total,int dp[])
19{
20
21 for(int j=1;j<=total;j++) //這是與上題的區(qū)別之處，因?yàn)檫@題要求的是最少,所以在初始化時
22dp[j]=1000000; //我選擇了1000000作為無窮大
23 dp[0]=0;
24 for(int p=1;p<=n;p++)
25 for(int q=total;q>=0;q--)
26 if(a[p]<=q)
27 dp[q]=min(dp[q],dp[q-a[p]]+1);
28 else
29 dp[q]=dp[q];
30
31 if(dp[total]!=1000000)
32 return dp[total];
33 else
34 return -1;
35 free(dp);
36
37}
38int main()
39{
40while(cin>>n)
41{
42 int *toy=new int[n+1];
43 for(int i=1;i<=n;i++)
44 cin>>toy[i];
45 cin>>sum;
46 int* dp=new int [sum+1];
47 cout<<zeroonepack(toy,sum,dp)<<endl;
48 free(toy);
49 free(dp);
50}
51 return 0;
52}
53
54
55
56/---------------------------------------------------------------------------------------------------------------------/
57 /---------------------------------------------------------------------------------------------------------------------/
58
59
完全背包
有了對0-1背包的深刻認(rèn)識，我們終于可以看看它的幾種變形了。首先登場的是完全背包，
何為“完全背包”，就是每樣?xùn)|西都有無窮多個.
我們還是先來到題目看看究竟吧!~
寒冰王座
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 1889 Accepted Submission(s): 810
Problem Description
不死族的巫妖王發(fā)工資拉,死亡騎士拿到一張N元的鈔票(記住,只有一張鈔票),為了防止自己在戰(zhàn)斗中頻繁的死掉,他決定給自己買一些道具,于是他來到了地精商店前.
死亡騎士:"我要買道具!"
地精商人:"我們這里有三種道具,血瓶150塊一個,魔法藥200塊一個,無敵藥水350塊一個."
死亡騎士:"好的,給我一個血瓶."
說完他掏出那張N元的大鈔遞給地精商人.
地精商人:"我忘了提醒你了,我們這里沒有找客人錢的習(xí)慣的,多的錢我們都當(dāng)小費(fèi)收了的,嘿嘿."
死亡騎士:"......"
死亡騎士想,與其把錢當(dāng)小費(fèi)送個他還不如自己多買一點(diǎn)道具,反正以后都要買的,早點(diǎn)買了放在家里也好,但是要盡量少讓他賺小費(fèi).
現(xiàn)在死亡騎士希望你能幫他計(jì)算一下,最少他要給地精商人多少小費(fèi).
Input
輸入數(shù)據(jù)的第一行是一個整數(shù)T(1<=T<=100),代表測試數(shù)據(jù)的數(shù)量.然后是T行測試數(shù)據(jù),每個測試數(shù)據(jù)只包含一個正整數(shù)N(1<=N<=10000),N代表死亡騎士手中鈔票的面值.
注意:地精商店只有題中描述的三種道具.
Output
對于每組測試數(shù)據(jù),請你輸出死亡騎士最少要浪費(fèi)多少錢給地精商人作為小費(fèi).
Sample Input
2
900
250
Sample Output
0
50
關(guān)鍵:
轉(zhuǎn)化為01背包問題求解
解題思路:
既然01背包問題是最基本的背包問題，那么我們可以考慮把完全背包問題轉(zhuǎn)化為01背包問題來解。最簡單的想法是，考慮到第i種物品最多選V/c[i]件，于是可以把第i種物品轉(zhuǎn)化為V/c[i]件費(fèi)用及價(jià)值均不變的物品，然后求解這個01背包問題。這樣完全沒有改進(jìn)基本思路的時間復(fù)雜度，但這畢竟給了我們將完全背包問題轉(zhuǎn)化為01背包問題的思路：將一種物品拆成多件物品。
但我們有更優(yōu)的O(VN)的算法。這個算法使用一維數(shù)組，先看偽代碼：
for i=1..N
for v=0..V
f[v]=max{f[v],f[v-c[i]]+w[i]};
你會發(fā)現(xiàn)，這個偽代碼與0-1背包的偽代碼只有v的循環(huán)次序不同而已。為什么這樣一改就可行呢？首先想想為什么0-1背包中要按照v=V..0的逆序來循環(huán)。這是因?yàn)橐ＷC第i次循環(huán)中的狀態(tài)f[i][v]是由狀態(tài)f[i-1][v-c[i]]遞推而來。換句話說，這正是為了保證每件物品只選一次，保證在考慮“選入第i件物品”這件策略時，依據(jù)的是一個絕無已經(jīng)選入第i件物品的子結(jié)果f[i-1][v-c[i]]。而現(xiàn)在完全背包的特點(diǎn)恰是每種物品可選無限件，所以在考慮“加選一件第i種物品”這種策略時，卻正需要一個可能已選入第i種物品的子結(jié)果f[i][v-c[i]]，所以就可以并且必須采用v=0..V的順序循環(huán)。這就是這個簡單的程序?yàn)楹纬闪⒌牡览怼?span lang=EN-US>
這個算法也可以以另外的思路得出。例如，基本思路中的狀態(tài)轉(zhuǎn)移方程可以等價(jià)地變形成這種形式：f[i][v]=max{f[i-1][v],f[i][v-c[i]]+w[i]}，將這個方程用一維數(shù)組實(shí)現(xiàn)，便得到了上面的偽代碼。
再看看我AC的代碼：
1/**//*
2copyright jj
3hdu-1248
4 2009.01.04
5 狀態(tài):已AC
6*/
7
8#include<iostream>
9using namespace std;
10int n=3,sum;
11int max(int a,int b){
12 int temp;
13 if(a>b) temp=a;
14 else temp=b;
15 return temp;
16}
17
18int completepack(int a[],int total,int dp[])
19{
20
21 for(int j=0;j<=total;j++)
22 dp[j]=0;
23 for(int p=1;p<=n;p++)
24 for(int q=0;q<=total;q++) //解決問題的關(guān)鍵點(diǎn)
25 if(a[p]<=q)
26 dp[q]=max(dp[q],dp[q-a[p]]+a[p]);
27 else
28 dp[q]=dp[q];
29
30 return dp[total];
31
32
33}
34int main()
35{
36 int toy[4]={0,150,200,350};
37 int m;
38while(cin>>m)
39{
40 for(int k=0;k<m;k++)
41 {
42 cin>>sum;
43 int* dp=new int [sum+1];
44 cout<<sum-completepack(toy,sum,dp)<<endl;
45 free(dp);
46 }
47
48
49}
50 return 0;
51}
52
53
54
55至于當(dāng)要求把背包完全裝滿該如何做，我就不再啰嗦了。可以參考0-1背包的解決辦法
56
57
58
59/---------------------------------------------------------------------------------------------------------------------/
60 /---------------------------------------------------------------------------------------------------------------------/
61
62
63
多重背包
當(dāng)每種物品不是1個也不是無窮多個，而是指定的n個時。就出現(xiàn)了我現(xiàn)在所要說的多重背包問題。
基本算法
這題目和完全背包問題很類似。基本的方程只需將完全背包問題的方程略微一改即可，因?yàn)閷τ诘?span lang=EN-US>i種物品有n[i]+1種策略：取0件，取1件……取n[i]件。令f[i][v]表示前i種物品恰放入一個容量為v的背包的最大權(quán)值，則有狀態(tài)轉(zhuǎn)移方程：
f[i][v]=max{f[i-1][v-k*c[i]]+k*w[i]|0<=k<=n[i]}
復(fù)雜度是O(V*Σn[i])。【好慢哦】
轉(zhuǎn)化為01背包問題
另一種好想好寫的基本方法是轉(zhuǎn)化為01背包求解：把第i種物品換成n[i]件01背包中的物品，則得到了物品數(shù)為Σn[i]的01背包問題，直接求解，復(fù)雜度仍然是O(V*Σn[i])。【依然是慢的】
來看一道題目:
Cash Machine
|
Time Limit: 1000MS
|
|
Memory Limit: 10000K
|
|
Total Submissions: 6470
|
|
Accepted: 2075
|
Description
A Bank plans to install a machine for cash withdrawal. The machine is able to deliver appropriate @ bills for a requested cash amount. The machine uses exactly N distinct bill denominations, say Dk, k=1,N, and for each denomination Dk the machine has a supply of nk bills. For example,
N=3, n1=10, D1=100, n2=4, D2=50, n3=5, D3=10
means the machine has a supply of 10 bills of @100 each, 4 bills of @50 each, and 5 bills of @10 each.
Call cash the requested amount of cash the machine should deliver and write a program that computes the maximum amount of cash less than or equal to cash that can be effectively delivered according to the available bill supply of the machine.
Notes:
@ is the symbol of the currency delivered by the machine. For instance, @ may stand for dollar, euro, pound etc.
Input
The program input is from standard input. Each data set in the input stands for a particular transaction and has the format:
cash N n1 D1 n2 D2 ... nN DN
where 0 <= cash <= 100000 is the amount of cash requested, 0 <=N <= 10 is the number of bill denominations and 0 <= nk <= 1000 is the number of available bills for the Dk denomination, 1 <= Dk <= 1000, k=1,N. White spaces can occur freely between the numbers in the input. The input data are correct.
Output
For each set of data the program prints the result to the standard output on a separate line as shown in the examples below.
Sample Input
735 3 4 125 6 5 3 350
633 4 500 30 6 100 1 5 0 1
735 0
0 3 10 100 10 50 10 10
Sample Output
735
630
0
0
是不是老是超時？怎么辦？怎么樣才能把O(V*Σn[i])的時間復(fù)雜度給降下來，還有什么地方可以剪枝嗎？
參考思路:
利用二進(jìn)制的思想，我們考慮把第i種物品換成若干件物品，使得原問題中第i種物品可取的每種策略——取0..n[i]件——均能等價(jià)于取若干件代換以后的物品。另外，取超過n[i]件的策略必不能出現(xiàn)。
方法是：將第i種物品分成若干件物品，其中每件物品有一個系數(shù)，這件物品的費(fèi)用和價(jià)值均是原來的費(fèi)用和價(jià)值乘以這個系數(shù)。使這些系數(shù)分別為1,2,4,...,2^(k-1),n[i]-2^k+1，且k是滿足n[i]-2^k+1>0的最大整數(shù)。例如，如果n[i]為13，就將這種物品分成系數(shù)分別為1,2,4,6的四件物品。
分成的這幾件物品的系數(shù)和為n[i]，表明不可能取多于n[i]件的第i種物品。另外這種方法也能保證對于0..n[i]間的每一個整數(shù)，均可以用若干個系數(shù)的和表示，這個證明可以分0..2^k-1和2^k..n[i]兩段來分別討論得出，并不難，希望你自己思考嘗試一下。
這樣就將第i種物品分成了O(log n[i])種物品，將原問題轉(zhuǎn)化為了復(fù)雜度為
O(V*Σlog n[i])的01背包問題，是很大的改進(jìn)。
下面給出O(log amount)時間處理一件多重背包中物品的過程，其中amount表示物品的數(shù)量：
procedure MultiplePack(cost,weight,amount)
if cost*amount>=V
CompletePack(cost,weight)
return
integer k=1
while k<amount
ZeroOnePack(k*cost,k*weight)
amount=amount-k
k=k*2
ZeroOnePack(amount*cost,amount*weight)
希望你仔細(xì)體會這個偽代碼，如果不太理解的話，看看下面我AC的程序，單步執(zhí)行幾次，或者頭腦加紙筆模擬一下，也許就會慢慢理解了。
再看看我AC的代碼,幫助你進(jìn)一步的理解這類問題:
1/**//*
2copyright jj
3pku-1276
4 2009.02.11
5 狀態(tài):已AC
6*/
7
8#include<iostream>
9using namespace std;
10
11
12int V;
13int huafei[11],n,geshu[11],*dp;
14
15int max(int a,int b){ return a>b?a:b;}
16void zeroonepack(int cost,int weight) //0-1背包的運(yùn)用
17{
18 for(int v1=V;v1>=0;v1--)
19 if(cost<=v1)
20 dp[v1]=max(dp[v1],dp[v1-cost]+weight);
21 else
22 dp[v1]=dp[v1];
23}
24
25void completepack(int cost,int weight) //完全背包的運(yùn)用
26{
27 for(int v2=0;v2<=V;v2++)
28 if(cost<=v2)
29 dp[v2]=max(dp[v2],dp[v2-cost]+weight);
30 else
31 dp[v2]=dp[v2];
32}
33
34
35void multiplepack(int cost ,int weight,int amount) //最后合成多重背包
36{
37 if(amount*cost>V)
38 {
39 completepack(cost,weight);
40 return ;
41 }
42
43 int k=1;
44 while(k<amount)
45 {
46 zeroonepack(k*cost,k*weight);
47 amount-=k;
48 k*=2;
49 }
50 zeroonepack(amount*cost,amount*weight);
51}
52
53int main()
54{
55 while(cin>>V>>n)
56 {
57 dp=new int[V+1];
58 for(int i=1;i<=n;i++)
59 cin>>geshu[i]>>huafei[i];
60 for(int q=0;q<=V;q++)
61 dp[q]=0;
62 for(int j=1;j<=n;j++)
63 multiplepack(huafei[j],huafei[j],geshu[j]);
64
65 cout<<dp[V]<<endl;
66 free(dp);
67 }
68 return 0;
69}
70
這樣O(log amount)的算法就搞定了。嘿嘿~
尾聲
關(guān)于背包問題的問法，我還想再多說兩句，但不做詳細(xì)的解釋,只供有興趣的人延伸閱讀
比如1：
要求你在輸出最優(yōu)方案的同時要求你把選擇的方案輸出?這該怎么做？
比如2：
要求你輸出字典序最小的最優(yōu)方案？又該怎么辦？
比如3：
要求你求出最優(yōu)方案的總數(shù)？那又是怎么樣的？
背包問題的變種還是非常多的,當(dāng)然都是在0-1背包的基礎(chǔ)上進(jìn)行修改的。在經(jīng)歷了去年的圣誕賽后，我也專門研究了一下各種背包問題。在學(xué)習(xí)過程中主要的參考資料是dd牛的《背包九講》,而以上的題目和代碼均為自己在學(xué)習(xí)過程中碰到并解決的，所以特別編輯在了一起希望以后學(xué)習(xí)背包的人能少走彎路。
Jj
2009-5-27