动态规划入门三---背包问题（1）

序言

背包问题是最广为人知的动态规划问题之一，拥有很多的变形，尽管在理解之后不难写出程序，但是往往要花费一定的时间真正的掌握它。

多阶段决策问题

1引例

物品无限的背包问题

有n种物品，每种均为无穷多个。第i个物品的体积为Vi,重量为Wi。选一些物品装入一个容量为C的背包，是的背包内的物品在总体积不超过C的情况下重量尽可能地大。

1<= n<= 100, 1<=C<=10000, 1<= Wi <= 1000000

【分析】

似乎很眼熟，因为这个就是之前的DAG的硬币问题扩展版，不过增加了一个属性重量。即是原来的无权图便成了有权图。

问题便成了求以C为起点的（终点任意）的，边权之和最大的路径。

此时最大的变化就是把原来的+1，变成了 + W[ i ] 。

2 0--1背包问题

有n种物品，每种只有一个。第i个物品的体积为Vi，重量为Wi。选一些物品装入一个容量为C的背包，是的背包内的物品在总体积不超过C的情况下重量尽可能地大。

1<= n<= 100, 1<=C<=10000, 1<= Wi <= 1000000 。

【分析】

此时可以发现，原来的只靠“剩余体积”这个状态，无法再做此题，因为不知道每个物品是否已经被用过。

也即是原来的状态转移太过混乱，任何时候均可以使用任何物品，所以，我们要把决策有序化！

【解决思想】

引入阶段的概念，具体参见回溯法的理解。

【算法设计】

用d(i，j) 表示当前在第i层，背包剩余剩余容量为j时候接下来的最大重量和，则就分为两种情况：第一种是把第j个物品放进去，此时背包的重量是d(i+1,j -V[ i ] ) + W[ i ] ,

第二种是不放第j个，此时背包的重量是：d（i+1，j）。

所以就有了下面的式子：

d(i，j) = max { d( i+1，j) ，d(i+1,j -V[ i ] ) + W[ i ] }

注意：这个递推的边界处理。下面的代码里面有提及。

提示：多阶段决策的最优化问题往往可以用动态规划来解决，其中，状态及其转移类似于回溯法的解答树。解答树中的“层数”，即是递归函数里面的“当前填充位置”，描述的是即将完成的决策序号，在DP中被称为阶段。。。

其实：说的白一点，所谓的d(i，j)代表的就是把第i个以及其后的n-i+1个物品装到容量为j的背包中的最大重量。

【算法程序代码】

第一个方法：递推法

关键代码如下：

	printf("请输入%d个物品的体积和重量:",n) ;
		for (i=1; i<=n; i ++)
		{
			scanf("%d%d", &v, &wei) ; // 新的状态定义f(i,j)允许我们边读入边计算，而不必把数值存入数组
			for (j=0; j<=c; j++)
			{
				f[i][j] = (i==1 ? 0 : f[i-1][j] );
				if (j >= v)
					if(f[i][j] < f[i-1][j-v] + wei)
						f[i][j] = (f[i-1][j-v] + wei);
			}
		}

第二个方法，一维数组解决。

先上代码：

    for(i=0;i<=n;i++)
    {
        for(j=c;j>=V[i];j--)
        {
            WEI[j]=max(WEI[j],WEI[j-V[i]]+ W[i]);
        }
    }
    printf("第一种的计算结果是：%d\n\n", WEI[c]);

实例实践

加入背包容积为5，

各个物品的体积为2,4,1

各个物品的重量为9,8,1

测试代码如下：

/***** 背包问题 ********/

/******** written by C_Shit_Hu ************/

////////////////动态规划///////////////

/****************************************************************************/
/* 
有n种物品，每种只有一个。第i个物品的体积为Vi，重量为Wi。
选一些物品装入一个容量为C的背包，是的背包内的物品在总体积不超过C的情况下重量尽可能地大。
1<= n<= 100,  1<=C<=10000, 1<= Wi <= 1000000 。
*/
/****************************************************************************/


// 三种算法
#include <stdio.h>
#include <string.h>
#define MAX 100
int V[MAX] , W[MAX],f[MAX][MAX], WEI[MAX] ;
int n, i, j, c, v, wei, ele; 

int max(int x,int y)
{return x>y ? x:y;}

int main()
{
	// 基本信息的输入
	printf("请输入您的背包的容积:");
	scanf("%d", &c);
	printf("请输入您要装入背包的物品种类数目:");
	scanf("%d", &n);
	
	// 第一种第二种需要的数据
	printf("请输入每种物品的体积(以空格隔开)：");
	for (i=0; i<n; i++)
		scanf("%d", &V[i]);
	printf("请输入每种物品的重量(以空格隔开)：");
	for (i=0; i<n; i++)
		scanf("%d", &W[i]);
	/* 原理介绍
	另外一种对称的状态定义:用f(i,j)表示“把前i个物品装入容量为j的背包中的最大重量和”，由此也可得其状态转移方程：
	f(i,j) == max ( f(i-1), f(i-1,j-V[i]) + W[i] )    // 同样是分为装或不装第i个
	边界是类似的：i=0时为0，j<0时为负无穷，最终答案是f(n, c).
	*/
	// 代码如下：
	for(i=0;i<=n;i++)
    {
        for(j=c;j>=V[i];j--)
        {
            WEI[j]=max(WEI[j],WEI[j-V[i]]+ W[i]);
        }
    }
    printf("第一种的计算结果是：%d\n\n", WEI[c]);
	printf("请输入%d个物品的体积和重量:",n) ;
	for (i=1; i<=n; i ++)
	{
		scanf("%d%d", &v, &wei) ; // 此处就是两种方法的区别：新的状态定义f(i,j)允许我们边读入边计算，而不必把数值存入数组
		for (j=0; j<=c; j++)
		{
			f[i][j] = (i==1 ? 0 : f[i-1][j] );
			if (j >= v)
				if(f[i][j] <= f[i-1][j-v] + wei)
					f[i][j] = (f[i-1][j-v] + wei);
		}
	}
	printf("第二种的计算结果是：%d\n\n", f[n][c]);
	return 0;
}


/******************************************************/
/********************  心得体会  **********************/
/*

*/
/******************************************************/

测试结果如下：

问题求助

下面代码的注释部分，觉得算法没有问题，为何就是结果不对呢？

/***** 背包问题 ********/

/******** written by C_Shit_Hu ************/

////////////////动态规划///////////////

/****************************************************************************/
/* 
有n种物品，每种只有一个。第i个物品的体积为Vi，重量为Wi。
选一些物品装入一个容量为C的背包，是的背包内的物品在总体积不超过C的情况下重量尽可能地大。
1<= n<= 100,  1<=C<=10000, 1<= Wi <= 1000000 。
*/
/****************************************************************************/


// 三种算法
#include <stdio.h>
#include <string.h>
#define MAX 100
int V[MAX] , W[MAX], d[MAX][MAX], f[MAX][MAX], h[MAX], WEI[MAX] ;
int n, i, j, c, v, wei, ele; 

int max(int x,int y)
{return x>y ? x:y;}

int main()
{
	// 基本信息的输入
	printf("请输入您的背包的容积:");
	scanf("%d", &c);
	printf("请输入您要装入背包的物品种类数目:");
	scanf("%d", &n);
	
	// 第一种第二种需要的数据
	printf("请输入每种物品的体积(以空格隔开)：");
	for (i=0; i<n; i++)
		scanf("%d", &V[i]);
	printf("请输入每种物品的重量(以空格隔开)：");
	for (i=0; i<n; i++)
		scanf("%d", &W[i]);
		/*   for (i=0; i<n; i++)
		printf("%d  ", V[i]);
		for (i=0; i<n; i++)
        printf("%d ",W[i]);
		// 第一种解决方案：递推思想解决,答案是d[1][c]
		for (i=n; i>=1; i--)
		for (j=0; j<=c; j++)
		{
		d[i][j] = (i==n ? 0 : d[i+1][j] );
		if (j >= V[i])
		if(d[i][j] < (d[i+1][j-V[i]] + W[i]))
		d[i][j] = ( d[i+1][j-V[i]] + W[i]);
		}
		for (i=n; i>=1; i--)
		for (j=0; j<=c; j++)
		printf("%d  ",d[i][j] );
		printf("\n\n第一种的计算结果是：%d\n\n", d[1][c]);
	*/	
	// 改变方向
	/* 原理介绍
	另外一种对称的状态定义:用f(i,j)表示“把前i个物品装入容量为j的背包中的最大重量和”，由此也可得其状态转移方程：
	f(i,j) == max ( f(i-1), f(i-1,j-V[i]) + W[i] )    // 同样是分为装或不装第i个
	边界是类似的：i=0时为0，j<0时为负无穷，最终答案是f(n, c).
	*/
	// 代码如下：
	for(i=0;i<=n;i++)
    {
        for(j=c;j>=V[i];j--)
        {
            WEI[j]=max(WEI[j],WEI[j-V[i]]+ W[i]);
        }
    }
    printf("第一种的计算结果是：%d\n\n", WEI[c]);
	printf("请输入%d个物品的体积和重量:",n) ;
	for (i=1; i<=n; i ++)
	{
		scanf("%d%d", &v, &wei) ; // 此处就是两种方法的区别：新的状态定义f(i,j)允许我们边读入边计算，而不必把数值存入数组
		for (j=0; j<=c; j++)
		{
			f[i][j] = (i==1 ? 0 : f[i-1][j] );
			if (j >= v)
				if(f[i][j] <= f[i-1][j-v] + wei)
					f[i][j] = (f[i-1][j-v] + wei);
		}
	}
	printf("第二种的计算结果是：%d\n\n", f[n][c]);
	/*
	//滚动数组方式
	// 代码如下：
	memset(h, 0, sizeof(h)) ;
	printf("请输入%d个物品的体积和重量:", n);
	for(i=1; i<=n; i++)
	{
	scanf("%d%d", &v, &wei) ; 
	for(j=c; j>=0; j--)
	if(j>=v)
				if (h[j] >= h[j-v]+wei)
				h[j] = h[j-v] + wei;
				}
				printf("第三种的计算结果是：%d\n", h[c]);
				
				  return 0 ;
	*/
}


/******************************************************/
/********************  心得体会  **********************/
/*

*/
/******************************************************/

下一步。。。经典背包问题九讲的学习。

【未完待续……】