0-1背包问题(回溯法)

时间:2022-04-10 04:22:18

1.问题描述:

     给定一组物品,每个物品都有自己的重量和价格,在背包容量一定时,我们如何选择,才能使得背包内物品的总价格最高。每个物体只有放入:1或不放入:0两种状态,所以叫0-1背包问题。

2.算法设计:(参考博客:http://www.cnblogs.com/qinyg/archive/2012/05/16/2505523.html)

------物品有n个,背包容量为C;

       分别用p[i]和w[i]存储第i种物品的价值和重量;

       用x[i]标记第i种物品是否装入背包,用bestx[i]存储第i种物品的最优装载方案;

------用递归函数Backtrack (i,cp,cw)来实现回溯法搜索子集树

(形式参数i表示递归深度,n用来控制递归深度,形式参数cp和cw表示当前总价值和总重量,bestp表示当前最优总价值)


① 若i >n,则算法搜索到一个叶子结点,判断当前总价值是否最优:
    若cp>bestp,更新当前最优总价值为当前总价值(即bestp=cp),更新
装载方案(即bestx[i]=x[i]( 1≤i≤n));

   否则结束;
②若i<=n:

 采用for循环对物品i装与不装两种情况进行讨论(0≤j≤1):

------j=0时,即不装入背包:
1> x[i]=j;
2> 若总重量不大于背包容量(即cw+x[i]*w[i]<=c)

           更新当前总价值和总重量(即cw+=w[i]*x[i],cp+=p[i]*x[i]), 对物品i+1调用递归函数Backtrack(i+1,cp,cw) 继续进行装载;
3> 函数Backtrack(i+1,cp,cw)调用结束后则返回当前总价值和总重量
(即 cw-=w[i]*x[i],cp-=p[i]*x[i]);
 ------j=1时,即装入背包:

重新从步骤1>执行;


------ 主函数调用一次backtrack(1,0,0)即可完成整个回溯搜索过程,最终得到的bestp和bestx[i]即为所求最大总价值和最优装载方案。

    代码是我找的,重新组织过,算是我的啦(请原谅我的无耻,毕竟这个代码已经相当简练了):

#include<stdio.h>
int n,c,bestp;//物品的个数,背包的容量,最大价值
int p[10000],w[10000],x[10000],bestx[10000];//物品的价值,物品的重量,x[i]暂存物品的选中情况,物品的选中情况

void Backtrack(int i,int cp,int cw)
{ //cw当前包内物品重量,cp当前包内物品价值
int j;
if(i>n)//回溯结束
{
if(cp>bestp)
{
bestp=cp;
for(i=0;i<=n;i++) bestx[i]=x[i];
}
}
else
for(j=0;j<=1;j++)
{
x[i]=j;
if(cw+x[i]*w[i]<=c)
{
cw+=w[i]*x[i];
cp+=p[i]*x[i];
Backtrack(i+1,cp,cw);
cw-=w[i]*x[i];
cp-=p[i]*x[i];
}
}
}

int main()
{
int i;
bestp=0;
printf("请输入背包最大容量:\n");
scanf("%d",&c);
printf("请输入物品个数:\n");
scanf("%d",&n);
printf("请依次输入物品的重量:\n");
for(i=1;i<=n;i++)
scanf("%d",&w[i]);
printf("请依次输入物品的价值:\n");
for(i=1;i<=n;i++)
scanf("%d",&p[i]);
Backtrack(1,0,0);
printf("最大价值为:\n");
printf("%d\n",bestp);
printf("被选中的物品依次是(0表示未选中,1表示选中)\n");
for(i=1;i<=n;i++)
printf("%d ",bestx[i]);
printf("\n");
return 0;
}
/*测试数据:
10
5
2 2 6 5 4
6 3 5 4 6
*/

0-1背包问题(回溯法)