0-1背包问题 回溯法

0-1背包问题 回溯法

一、项目描述
每种物品只有2 种选择，分别为：装入背包或不装入背包，物品数和背包容量已给定，计算装入背包物品的最大价值和最优装入方案，用回溯法搜索子集树的算法进行求解。
二、算法设计
a. 物品有n种，背包容量为C，分别用p[i]和w[i]存储第i种物品的价值和重量，用x[i]标记第i种物品是否装入背包，用bestx[i]存储第i种物品的最优装载方案；

b. 用递归函数Backtrack (i,cp,cw)来实现回溯法搜索子集树（形式参数i表示递归深度，n用来控制递归深度，形式参数cp和cw表示当前总价值和总重量，bestp表示当前最优总价值）：
① 若i >n，则算法搜索到一个叶结点，判断当前总价值是否最优：
1> 若cp>bestp，更新当前最优总价值为当前总价值（即bestp=cp），更新装载方案（即bestx[i]=x）；

② 采用for循环对物品i装与不装两种情况进行讨论（0≤j≤1）：

1> x[i]=j；

2> 若总重量不大于背包容量（即cw+x[i]*w[i]<=c），则更新当前总价 br=”“> 值和总重量（即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]）；
4> 当j>1时，for循环结束；
③ 当i=1时，若已测试完所有装载方案，外层调用就全部结束；
c. 主函数调用一次backtrack(1,0,0)即可完成整个回溯搜索过程，最终得到的bestp和bestx[i]即为所求最大总价值和最优装载方案。
三、程序

方法1

#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%d",&n,&c);
    printf("请依次输入物品的价值:\n");
    for(i=1;i<=n;i++) 
        scanf("%d",&p[i]);
printf("请依次输入物品的重量:\n");
    for(i=1;i<=n;i++) 
        scanf("%d",&w[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;
}

四、复杂度分析
深度优先搜索的策略，
算法从Backtrack(1,0,0) 开始，调用void Backtrack(int i,int cp,int cw)函数，
当n = 1时，直接就根据物品重量与背包重量比较，只执行一步O(n)=O(1);
当n > 1时，进入for循环

for(j=0;j<=1; ++j)  // 枚举i所有可能的路径，

在满足限界函数和约束条件if(cw+x[i]*w[i]<=c)下，连续排列，直到碰壁，然后进行下一条路（另一个条件），进行下一次的遍历，直到结束，如图

()

最坏情况下有O（2n）个右儿子结点用限界函数，故计算0-1背包问题的回溯算法的时间复杂度为O(n2的n次方)，在搜索过程中的任何时刻，仅保留从开始结点到当前可扩展结点的路径，其空间需求为O（从开始结点起最长路径的长度）。所以，空间复杂度为O（n）