背包问题的应用

http://acm.hdu.edu.cn/showproblem.php?pid=2602Bone Collector

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

这是一个最简单的01背包问题。

#include <iostream>
using namespace std;

const int MAX = 10010;
int f[MAX];
int V;    //背包的体积

void ZeroOnePack (int cost, int weight)
{
    int v;
    for (v = V; v >= cost; v--)
        f[v] = f[v] > (f[v - cost] + weight) ? f[v] : (f[v - cost] + weight);
}

int value[1005],volume[1005];

int main(void)
{
	int t,num,i;
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d %d",&num,&V);
		for(i=0;i<=V;i++)      //没有要求把背包装满
		{
			f[i]=0;
		}
		for(i=1;i<=num;i++)
			scanf("%d",&value[i]);
		for(i=1;i<=num;i++)
			scanf("%d",&volume[i]);
		for(i=1;i<=num;i++)
			ZeroOnePack(volume[i], value[i]);
		printf("%d\n",f[V]);
	}
	return 0;
}

http://acm.zjut.edu.cn/ShowProblem.aspx?ShowID=1355擎天柱
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
这是浙工大ACM上的题目做完可以提交试试。。

想用刚才的方法做？发现题目里多了什么条件没？

对了！那就是“只有月光拿出的玩具的总价格与“擎天柱”的价格相等才能换得“擎天柱”这句。 换句话说题目要求的不仅仅是最优值而且要求你求的是“能把包装满”的最优值！！！

怎么办？难道就这样束手无策了么？

解答:

0-1背包也是背包问题的最常见的两种问法:

一是要求“恰好装满背包”时的最优解

二是“没有要求必须把背包装满”。

这两种问法的实现方法不同点主要在初始化上。

如果是第一种问法，要求恰好装满背包，那么在初始化时除了f[0]为0其它f[1..V]均设为-∞，这样就可以保证最终得到的f[N]是一种恰好装满背包的最优解。

如果并没有要求必须把背包装满，而是只希望价格尽量大，初始化时应该将f[0..V]全部设为0。
为什么呢？

可以这样理解：初始化的f数组事实上就是在没有任何物品可以放入背包时的合法状态。如果要求背包恰好装满，那么此时只有容量为0的背包可能被价值为0的nothing“恰好装满”，其它容量的背包均没有合法的解，属于未定义的状态，它们的值就都应该是-∞了。如果背包并非必须被装满，那么任何容量的背包都有一个合法解“什么都不装”，这个解的价值为0，所以初始时状态的值也就全部为0了。

这个小技巧完全可以推广到其它类型的背包问题，后面也就不再对进行状态转移之前的初始化进行讲解。

#include <stdio.h>
#include <stdlib.h>

const int MAX = 10010;
int f[MAX];
int V;    //背包的体积

void ZeroOnePack (int cost, int weight)
{
    int v;
    for (v = V; v >= cost; v--)
        f[v] = f[v] < (f[v - cost] + weight) ? f[v] : (f[v - cost] + weight);    //这里取较小的那个值
}

int value[15];

int main(void)
{
	int num,i;
	while(scanf("%d",&num)==1)
	{
		for(i=1;i<=num;i++)
			scanf("%d",&value[i]);
		scanf("%d",&V);

		f[0]=0;
		for(i=1;i<=V;i++)      //要求把背包装满
		{
			f[i]=0x3f;        //初始化为一个比较大的值
		}

		for(i=1;i<=num;i++)
			ZeroOnePack(value[i],1);

		if(f[V]!=0x3f)
			printf("%d\n",f[V]);
		else
			printf("-1\n");
	}
	return 0;
}

完全背包的应用：

有了对0-1背包的深刻认识，我们终于可以看看它的几种变形了。首先登场的是完全背包，何为“完全背包”，就是每样东西都有无穷多个。

我们还是先来到题目看看究竟吧！~

http://acm.hdu.edu.cn/showproblem.php?pid=1248 寒冰王座

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的代码：

#include <stdio.h>
#include <stdlib.h>

const int MAX = 10010;
int f[MAX];   //MAX要比背包的体积大
int V;        //背包的体积

void CompletePack (int cost, int weight)     //完全背包
{
    int v;
    for (v = cost; v <= V; v++)
        f[v] = f[v] > (f[v - cost] + weight) ? f[v] : (f[v - cost] + weight);    
}

int value[4]={0,150,200,350};

int main(void)
{
	int t,i;
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d",&V);

		for(i=0;i<=V;i++)      //没有要求把背包装满
		{
			f[i]=0;
		}

		for(i=1;i<=3;i++)
			CompletePack(value[i],value[i]);
		
		printf("%d\n",V-f[V]);
	}
	return 0;
}

多重背包
当每种物品不是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])。【依然是慢的】

参考思路：

利用二进制的思想，我们考虑把第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的程序，单步执行几次，或者头脑加纸笔模拟一下，也许就会慢慢理解了。
http://acm.hdu.edu.cn/showproblem.php?pid=2191

Problem Description
急！灾区的食物依然短缺！
为了挽救灾区同胞的生命，心系灾区同胞的你准备自己采购一些粮食支援灾区，现在假设你一共有资金n元，而市场有m种大米，每种大米都是袋装产品，其价格不等，并且只能整袋购买。
请问：你用有限的资金最多能采购多少公斤粮食呢？

后记：
人生是一个充满了变数的生命过程，天灾、人祸、病痛是我们生命历程中不可预知的威胁。
月有阴晴圆缺，人有旦夕祸福，未来对于我们而言是一个未知数。那么，我们要做的就应该是珍惜现在，感恩生活——
感谢父母，他们给予我们生命，抚养我们成人；
感谢老师，他们授给我们知识，教我们做人
感谢朋友，他们让我们感受到世界的温暖；
感谢对手，他们令我们不断进取、努力。
同样，我们也要感谢痛苦与艰辛带给我们的财富～
Input
输入数据首先包含一个正整数C，表示有C组测试用例，每组测试用例的第一行是两个整数n和m(1<=n<=100, 1<=m<=100),分别表示经费的金额和大米的种类，然后是m行数据，每行包含3个数p，h和c(1<=p<=20,1<=h<=200,1<=c<=20)，分别表示每袋的价格、每袋的重量以及对应种类大米的袋数。
Output
对于每组测试数据，请输出能够购买大米的最多重量，你可以假设经费买不光所有的大米，并且经费你可以不用完。每个实例的输出占一行。
Sample Input
1
8 2
2 100 4
4 100 2
Sample Output
400

再看看我AC的代码，帮助你进一步的理解这类问题：

#include <stdio.h>
#include <stdlib.h>

int V;        //背包的体积
const int MAX = 10010;
int f[MAX];   //MAX要比背包的体积大
int p[MAX], h[MAX], c[MAX];

void ZeroOnePack (int cost, int weight)      //01背包
{
    int v;
    for (v = V; v >= cost; v--)
        f[v] = f[v] > (f[v - cost] + weight) ? f[v] : (f[v - cost] + weight);
}

void CompletePack (int cost, int weight)     //完全背包
{
    int v;
    for (v = cost; v <= V; v++)
        f[v] = f[v] > (f[v - cost] + weight) ? f[v] : (f[v - cost] + weight);    
}

void MultiplePack(int cost, int weight, int amount)     //多重背包
{
    if (cost * amount >= V)
        CompletePack (cost, weight);
    int k = 1;
    while (k < amount)
    {
        ZeroOnePack (k * cost, k * weight);
        amount = amount - k;
        k = k * 2;
    }
    ZeroOnePack (amount * cost, amount * weight);    
}

int main(void)
{
	int t,i,m;
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d %d",&V,&m);

		for(i=0;i<=V;i++)      //没有要求把背包装满
		{
			f[i]=0;
		}
		for(i=1;i<=m;i++)
			scanf("%d %d %d",&p[i],&h[i],&c[i]);

		for(i=1;i<=m;i++)
			MultiplePack(p[i], h[i], c[i]);
		
		printf("%d\n",f[V]);
	}
	return 0;
}