一分钟让你快速学会的简单算法（如何用两种经典算法实现背包问题）

一分钟让你快速学会的简单算法（如何用两种经典算法实现背包问题）问题描述：假设有一个背包最多能装8 kg物体，假设要使背包能装下下面的水果，并要求背包里面的水果价值最大，问应该装哪些水果符合要求？实例　使用递归法解决“背包”问题计算最大价值的动态规划算法如下所示。 //计算 for(i=1;i<row;i ) ...{ for(j=1;j<col;j ) ...{ //w[i]>j 第i个物品不装入背包 value[i][j]=value[i-1][j]; //w[i]<=j 且第i个物品装入背包后的价值>value[i-1][j] 则记录当前最大价值 int temp=value[i-1][j-w[i]] v[i]; if(w[i]<=j && temp>value[i][j]) value[i][j]=temp; } } 上述程序段完成以下n个阶段。图12　使用动

背包问题

背包问题是在1978年由Merkel和Hellman提出的，主要思路是假设某人拥有大量物品，物品的重量都不相同。此人通过秘密地选择一部分物品，并将物品放到背包中来加密消息。背包中物品的重量是公开的，所有可能的物品也是公开的，但背包中装的物品种类是保密的。背包问题的题目要求是：给定一组物品，每种物品都有自己的重量和价格，在限定的总重量内，如何选择才能使物品的总价格最高。

1　使用动态规划法

实例　使用动态规划法解决“背包”问题

问题描述：设定一个载重量为m，有n个物品，其重量为wi，价值为vi，1<=i<=n，要求把物品装入背包，并使包内物品价值最大。

算法分析：在背包问题中，物品要么被装入背包，要么不被装入背包。设置循环变量i，前i个物品能够装入载重量为j的背包中。用value[i][j]数组表示前i个物品能装入载重量为j的背包中物品的最大价值。如果w[i]>j，第i个物品不装入背包；如果w[i]<=j且第i个物品装入背包后的价值>value[i−1][j]，则记录当前最大价值（替换为第i个物品装入背包后的价值）

计算最大价值的动态规划算法如下所示。

//计算 for(i=1;i<row;i ) ...{ for(j=1;j<col;j ) ...{ //w[i]>j 第i个物品不装入背包 value[i][j]=value[i-1][j]; //w[i]<=j 且第i个物品装入背包后的价值>value[i-1][j] 则记录当前最大价值 int temp=value[i-1][j-w[i]] v[i]; if(w[i]<=j && temp>value[i][j]) value[i][j]=temp; } }

上述程序段完成以下n个阶段。

图12　使用动态规划法解决“背包”问题执行效果

2　使用递归法

实例　使用递归法解决“背包”问题

问题描述：假设有一个背包最多能装8 kg物体，假设要使背包能装下下面的水果，并要求背包里面的水果价值最大，问应该装哪些水果符合要求？

• 苹果：5 kg，40元。
• 梨：2 kg，12元。
• 桃：1 kg，7元。
• 葡萄：1 kg，8元。
• 香蕉：6 kg，48元。

具体实现：编写实例文件13-3.c，其具体实现流程如下所示。

（1）定义结构goods来保存水果的相关信息，具体实现代码如下所示。

typedef struct goods { double *value; //价值 double *weight; //重量 char *select; //是否选中到方案 int num; //物品数量 double limitw; //限制重量 }GOODS;

（2）分别定义全局变量maxvalue、totalvalue和select1，然后定义函数backpack()通过递归方法完成背包的装入操作。具体实现代码如下所示。

double maxvalue totalvalue;//方案最大价值 物品总价值 char *select1; //临时数组 //参数为物品i 当前选择已经达到的重量和tw 本方案可能达到的总价值 void backpack(GOODS *g int i double tw double tv) { int k; if (tw g->weight[i] <= g->limitw)//将物品i包含在当前方案 且重量小于等于限制重量 { select1[i] = 1; //选中第i个物品 if (i < g->num - 1) //若物品i不是最后一个物品 backpack(g i 1 tw g->weight[i] tv); //递归调用 继续添加下一物品 else //如果已到最后一个物品 { for (k = 0; k < g->num; k) //将状态标志复制到选择数组中 g->select[k] = select1[k]; maxvalue = tv; //保存当前方案的最大价值 } } select1[i] = 0; //取消物品i的选择状态 //如果物品总价值减去物品i的价值还大于maxvalu方案中已有的价值 说明还可以继续向方案中添加物品 if (tv - g->value[i] > maxvalue) { if (i < g->num - 1) //若物品i不是最后一个物品 backpack(g i 1 tw tv - g->value[i]); //递归调用 继续加入下一物品 else //若已到最后一个物品 { for (k = 0; k < g->num; k) //将状态标志复制到选择数组中 g->select[k] = select1[k]; //保存当前方案的最大价值(从物品总价值中减去物品i的价值) maxvalue = tv - g->value[i]; } } }

（3）定义主函数main()调用上面定义的函数实现背包求解，具体实现代码如下所示。

int main() { double sumweight; GOODS g; int i; printf("背包最大重量:"); scanf("%lf" &g.limitw); printf("可选物品数量:"); scanf("%d" &g.num); if(!(g.value = (double *)malloc(sizeof(double)*g.num)))//分配内存保存物品价值 { printf("内存分配失败\n"); exit(0); } if(!(g.weight = (double *)malloc(sizeof(double)*g.num)))//分配内存保存物品的重量 { printf("内存分配失败\n"); exit(0); } if(!(g.select = (char *)malloc(sizeof(char)*g.num))) //分配内存保存物品的重量（选中方案的重量） { printf("内存分配失败\n"); exit(0); } if(!(select1 = (char *)malloc(sizeof(char)*g.num))) //分配内存保存物品的重量（某类选择物体） { printf("内存分配失败\n"); exit(0); } totalvalue=0; for (i = 0; i < g.num; i ) { printf("输入第%d号物品的重量和价值:" i 1); scanf("%lf%lf" &g.weight[i] &g.value[i]); totalvalue =g.value[i];//统计所有物品的价值总和 } printf("\n背包最大能装的重量为:%.2f\n\n" g.limitw); for (i = 0; i < g.num; i ) printf("第%d号物品重:%.2f 价值:%.2f\n" i 1 g.weight[i] g.value[i]); for (i = 0; i < g.num; i )//初始设各物品都没加入选择集 select1[i]=0; maxvalue=0;//加入方案物品的总价值 backpack(&g 0 0.0 totalvalue); //第0号物品加入方案 总重量为0 所有物品价值为totalvalue sumweight=0; printf("\n可将以下物品装入背包 使背包装的物品价值最大:\n"); for (i = 0; i < g.num; i) if (g.select[i]) { printf("第%d号物品 重量:%.2f 价值:%.2f\n" i 1 g.weight[i] g.value[i]); sumweight =g.weight[i]; } printf("\n总重量为: %.2f 总价值为:%.2f\n" sumweight maxvalue ); getch(); return 0; }

执行后的效果如图13-3所示。

图3　使用递归法解决“背包”问题执行效果