记得去年的校圣诞编程大赛的初赛和复赛中有3，4道类型相似的题目，当时对于刚加入ACMER行列的我并不了解这是哪一类的题目，只觉得这些题目有一定的规律。后来写的程序多了，接触的算法也多了，慢慢的知道那3，4道题目其实是动态规划下的”背包问题”.现在基本上了解了这类题目的解题思路和应对方法,故想借此对各种背包问题做一个详细的解释.
0-1背包
0-1背包是基础,接下来所有背包的问题都会围绕0-1背包展开,所以我将会特别仔细的进行阐释.当然0-1背包可以用贪心来完成,考虑到各种背包的通用性,贪心解法我就略过了,直接从动态规划的解法开始讲起.
先从一道例题讲起:
0-1原型:
一个旅行者有一个最多能用M公斤的背包，现在有N件物品，
它们的重量分别是W1，W2，...,Wn,
它们的价值分别为P1,P2,...,Pn.
问:每种物品只有一件，则旅行者能获得的最大总价值是多少?
解答:
其实很多人都能从网上搜到0-1背包的状态转移方程,即: f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]}.但是对它的灵活运用和具体实现不甚了解，接下来我以这题为例展示此状态方程的由来，以便接下来后面几种背包的学习.
因为背包最大容量M未知。所以，我们的程序要从1到M一个一个的试。比如，开始任选N件物品的一个。看对应M的背包，能不能放进去，如果能放进去，并且还有多的空间，则，多出来的空间里能放N-1物品中的最大价值。怎么能保证总选择是最大价值呢？
看下表。
测试数据：
10,3
3,4
4,5
5,6
c[i][j]数组保存了1,2,3号物品依次选择后的最大价值.
这个最大价值是怎么得来的呢?从背包容量为0开始,1号物品先试,0,1,2,的容量都不能放.所以置0,背包容量为3则里面放4.这样,这一排背包容量为4,5,6,....10的时候，最佳方案都是放4.假如1号物品放入背包.则再看2号物品.当背包容量为3的时候，最佳方案还是上一排的最价方案c为4.而背包容量为5的时候，则最佳方案为自己的重量5.背包容量为7的时候，很显然是5加上一个值了。加谁??很显然是7-4=3的时候.上一排 c3的最佳方案是4.所以。总的最佳方案是5+4为9.这样.一排一排推下去。最右下放的数据就是最大的价值了。(注意第3排的背包容量为7的时候,最佳方案不是本身的6.而是上一排的9.说明这时候3号物品没有被选.选的是1,2号物品.所以得9.)
从以上最大价值的构造过程中可以看出。
f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]} 这就是0-1背包的状态转移方程了
/以下是实际程序，此程序来源自网络
1
/-----------------------------------------------------------------------------------/
2#include<stdio.h>
3
int c[10][100];/**//*对应每种情况的最大价值*/
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;/**//*初始化数组*/
12 for(i=1;i<n+1;i++)
13 for(j=1;j<m+1;j++)
14 {
15 if(w[i]<=j) /**//*如果当前物品的容量小于背包容量*/
16 {
17 if(p[i]+c[i-1][j-w[i]]>c[i-1][j])
18 /**//*如果本物品的价值加上背包剩下的空间能放的物品的价值*/
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");/**//*下面是测试这个数组,可删除*/
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
好了继续，看完上面的解释，相信你对0-1背包的运作有了基本的了解，下面就来练练手吧.
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 状态:已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++) //注意循环的始末
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]); //最关键的状态转移方程
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
如果不懂上述代码,请再回看图片,接下来我们再来看一道题目
擎天柱
Time Limit:1000MS Memory Limit:32768K
Description:
话说月光家里有许多玩具，最近他又看上了DK新买的“擎天柱”，就想用自己的跟DK的换。每种玩具都有特定的价格，价格为整数。只有月光拿出的玩具的总价格与“擎天柱”的价格相等才能换得“擎天柱”。同时，月光还希望能用最少的玩具数换回“擎天柱”。请问，月光能顺利得到梦寐以求的“擎天柱”吗？
Input:
输入数据包含多组；对于每组数据，第一行为一个正整数n(1 ≤n≤10); 表示月光手头有n个玩具。接下来一行有n个正整数P1，P2，……，Pn（1 ≤ Pi ≤ 1000），Pi为第i个玩具的所对应的价格。最后一行为一个正整数m(1 ≤ m ≤10000)，为“擎天柱”的价格。
Output:
对于每组数据，如果能换得“擎天柱”则输出最少玩具数；否则，输出“-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
祝你好运！~
想用刚才的方法做？发现题目里多了什么条件没？
对了！那就是“只有月光拿出的玩具的总价格与“擎天柱”的价格相等才能换得“擎天柱””这句。 换句话说题目要求的不仅仅是最优值而且要求你求的是“能把包装满”的最优值！！！
怎么办？难道就这样束手无策了么？
解答:
0-1背包也是背包问题的最常见的两种问法:
一是要求“恰好装满背包”时的最优解
二是“没有要求必须把背包装满”。
这两种问法的实现方法不同点主要在初始化上。
如果是第一种问法，要求恰好装满背包，那么在初始化时除了f[0]为0其它f[1..V]均设为-∞，这样就可以保证最终得到的f[N]是一种恰好装满背包的最优解。
如果并没有要求必须把背包装满，而是只希望价格尽量大，初始化时应该将f[0..V]全部设为0。
为什么呢？
可以这样理解：初始化的f数组事实上就是在没有任何物品可以放入背包时的合法状态。如果要求背包恰好装满，那么此时只有容量为0的背包可能被价值为0的nothing“恰好装满”，其它容量的背包均没有合法的解，属于未定义的状态，它们的值就都应该是-∞了。如果背包并非必须被装满，那么任何容量的背包都有一个合法解“什么都不装”，这个解的价值为0，所以初始时状态的值也就全部为0了。
这个小技巧完全可以推广到其它类型的背包问题，后面也就不再对进行状态转移之前的初始化进行讲解
再来看看我AC的代码:
1/**//*
2copyright jj
3zjut-1355
4 2009.01.03
5 状态:已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++) //这是与上题的区别之处，因为这题要求的是最少,所以在初始化时
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背包的深刻认识，我们终于可以看看它的几种变形了。首先登场的是完全背包，
何为“完全背包”，就是每样东西都有无穷多个.
我们还是先来到题目看看究竟吧!~
寒冰王座
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 1889 Accepted Submission(s): 810
Problem Description
不死族的巫妖王发工资拉,死亡骑士拿到一张N元的钞票(记住,只有一张钞票),为了防止自己在战斗中频繁的死掉,他决定给自己买一些道具,于是他来到了地精商店前.
死亡骑士:"我要买道具!"
地精商人:"我们这里有三种道具,血瓶150块一个,魔法药200块一个,无敌药水350块一个."
死亡骑士:"好的,给我一个血瓶."
说完他掏出那张N元的大钞递给地精商人.
地精商人:"我忘了提醒你了,我们这里没有找客人钱的习惯的,多的钱我们都当小费收了的,嘿嘿."
死亡骑士:"......"
死亡骑士想,与其把钱当小费送个他还不如自己多买一点道具,反正以后都要买的,早点买了放在家里也好,但是要尽量少让他赚小费.
现在死亡骑士希望你能帮他计算一下,最少他要给地精商人多少小费.
Input
输入数据的第一行是一个整数T(1<=T<=100),代表测试数据的数量.然后是T行测试数据,每个测试数据只包含一个正整数N(1<=N<=10000),N代表死亡骑士手中钞票的面值.
注意:地精商店只有题中描述的三种道具.
Output
对于每组测试数据,请你输出死亡骑士最少要浪费多少钱给地精商人作为小费.
Sample Input
2
900
250
Sample Output
0
50
关键:
转化为01背包问题求解
解题思路:
既然01背包问题是最基本的背包问题，那么我们可以考虑把完全背包问题转化为01背包问题来解。最简单的想法是，考虑到第i种物品最多选V/c[i]件，于是可以把第i种物品转化为V/c[i]件费用及价值均不变的物品，然后求解这个01背包问题。这样完全没有改进基本思路的时间复杂度，但这毕竟给了我们将完全背包问题转化为01背包问题的思路：将一种物品拆成多件物品。
但我们有更优的O(VN)的算法。这个算法使用一维数组，先看伪代码：
for i=1..N
for v=0..V
f[v]=max{f[v],f[v-c[i]]+w[i]};
你会发现，这个伪代码与0-1背包的伪代码只有v的循环次序不同而已。为什么这样一改就可行呢？首先想想为什么0-1背包中要按照v=V..0的逆序来循环。这是因为要保证第i次循环中的状态f[i][v]是由状态f[i-1][v-c[i]]递推而来。换句话说，这正是为了保证每件物品只选一次，保证在考虑“选入第i件物品”这件策略时，依据的是一个绝无已经选入第i件物品的子结果f[i-1][v-c[i]]。而现在完全背包的特点恰是每种物品可选无限件，所以在考虑“加选一件第i种物品”这种策略时，却正需要一个可能已选入第i种物品的子结果f[i][v-c[i]]，所以就可以并且必须采用v=0..V的顺序循环。这就是这个简单的程序为何成立的道理。
这个算法也可以以另外的思路得出。例如，基本思路中的状态转移方程可以等价地变形成这种形式：f[i][v]=max{f[i-1][v],f[i][v-c[i]]+w[i]}，将这个方程用一维数组实现，便得到了上面的伪代码。
再看看我AC的代码：
1/**//*
2copyright jj
3hdu-1248
4 2009.01.04
5 状态:已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++) //解决问题的关键点
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至于当要求把背包完全装满该如何做，我就不再啰嗦了。可以参考0-1背包的解决办法
56
57
58
59/---------------------------------------------------------------------------------------------------------------------/
60 /---------------------------------------------------------------------------------------------------------------------/
61
62
63
多重背包
当每种物品不是1个也不是无穷多个，而是指定的n个时。就出现了我现在所要说的多重背包问题。
基本算法
这题目和完全背包问题很类似。基本的方程只需将完全背包问题的方程略微一改即可，因为对于第i种物品有n[i]+1种策略：取0件，取1件……取n[i]件。令f[i][v]表示前i种物品恰放入一个容量为v的背包的最大权值，则有状态转移方程：
f[i][v]=max{f[i-1][v-k*c[i]]+k*w[i]|0<=k<=n[i]}
复杂度是O(V*Σn[i])。【好慢哦】
转化为01背包问题
另一种好想好写的基本方法是转化为01背包求解：把第i种物品换成n[i]件01背包中的物品，则得到了物品数为Σn[i]的01背包问题，直接求解，复杂度仍然是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])的时间复杂度给降下来，还有什么地方可以剪枝吗？
参考思路:
利用二进制的思想，我们考虑把第i种物品换成若干件物品，使得原问题中第i种物品可取的每种策略——取0..n[i]件——均能等价于取若干件代换以后的物品。另外，取超过n[i]件的策略必不能出现。
方法是：将第i种物品分成若干件物品，其中每件物品有一个系数，这件物品的费用和价值均是原来的费用和价值乘以这个系数。使这些系数分别为1,2,4,...,2^(k-1),n[i]-2^k+1，且k是满足n[i]-2^k+1>0的最大整数。例如，如果n[i]为13，就将这种物品分成系数分别为1,2,4,6的四件物品。
分成的这几件物品的系数和为n[i]，表明不可能取多于n[i]件的第i种物品。另外这种方法也能保证对于0..n[i]间的每一个整数，均可以用若干个系数的和表示，这个证明可以分0..2^k-1和2^k..n[i]两段来分别讨论得出，并不难，希望你自己思考尝试一下。
这样就将第i种物品分成了O(log n[i])种物品，将原问题转化为了复杂度为
O(V*Σlog n[i])的01背包问题，是很大的改进。
下面给出O(log amount)时间处理一件多重背包中物品的过程，其中amount表示物品的数量：
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)
希望你仔细体会这个伪代码，如果不太理解的话，看看下面我AC的程序，单步执行几次，或者头脑加纸笔模拟一下，也许就会慢慢理解了。
再看看我AC的代码,帮助你进一步的理解这类问题:
1/**//*
2copyright jj
3pku-1276
4 2009.02.11
5 状态:已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背包的运用
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) //完全背包的运用
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)的算法就搞定了。嘿嘿~
尾声
关于背包问题的问法，我还想再多说两句，但不做详细的解释,只供有兴趣的人延伸阅读
比如1：
要求你在输出最优方案的同时要求你把选择的方案输出?这该怎么做？
比如2：
要求你输出字典序最小的最优方案？又该怎么办？
比如3：
要求你求出最优方案的总数？那又是怎么样的？
背包问题的变种还是非常多的,当然都是在0-1背包的基础上进行修改的。在经历了去年的圣诞赛后，我也专门研究了一下各种背包问题。在学习过程中主要的参考资料是dd牛的《背包九讲》,而以上的题目和代码均为自己在学习过程中碰到并解决的，所以特别编辑在了一起希望以后学习背包的人能少走弯路。
Jj
2009-5-27