回溯法求解0-1背包问题

回溯法求解0-1背包问题时比较随机序列和按 v/w 降序排列的算法

问题描述：

针对0-1背包问题，尝试用回溯法。

物品总数N=10,背包容量 C=26, 物品的重量数组为w={7，3，10，12，1，5，7，3，6, 4}, 相应物品价值数组为:v={20,6,15,20,12,10,17,6,3,10} 。

试比较随机序列和按 v/w 降序排列的算法访问节点的个数的差异。

代码实现：

/*
回溯法背包问题 
比较随机序列和按 v/w 降序排列的算法访问节点的个数的差异 
N=10, C=26, w={7,3,10,12,1,5,7,3,6,4}, v={20,6,15,20,12,10,17,6,3,10} 
*/

#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <cstdlib> 
#include <ctime>
int  fluet=0;
//#include <conio.h>
using namespace std;
int n=10;//物品数量
double c=26;//背包容量
double w[]={0,7,3,10,12,1,5,7,3,6,4};//各个物品的重量　weight
double v[]={0,20,6,15,20,12,10,17,6,3,10}; //各个物品的价值　value
//double v[100];//各个物品的价值　value
//double w[100];//各个物品的重量　weight
double cw = 0;//当前背包重量　current weight
double cp = 0;//当前背包中物品总价值　current value
double bestp = 0;//当前最优价值best price
double perp[100];//单位物品价值(排序后) per price
int order[100];//物品编号
int best_x[100];//用于记录回溯过程的最优情况
int x[100];//设置是否装入，为1的时候表示选择该组数据装入，为0的表示不选择该组数据
 
 
//按单位价值排序
void knapsack()
{
    int i,j;
    int temporder = 0;
    double temp = 0;
 
    for(i=1;i<=n;i++)
        perp[i]=v[i]/w[i]; //计算单位重量的物品价值
    for(i=1;i<=n-1;i++)
    {
        for(j=i+1;j<=n;j++)
            if(perp[i]<perp[j])//冒泡排序perp[],order[],sortv[],sortw[]
        {
            temp = perp[i];  //冒泡对perp[]排序
            perp[i]=perp[j];
            perp[j]=temp;
 
            temporder=order[i];//冒泡对order[]排序
            order[i]=order[j];
            order[j]=temporder;
 
            temp = v[i];//冒泡对v[]排序
            v[i]=v[j];
            v[j]=temp;
 
            temp=w[i];//冒泡对w[]排序
            w[i]=w[j];
            w[j]=temp;
        }
    }
    cout<<"按单位价值排序后顺序："<<endl;
       for(i=1;i<=n;i++)
    {
            cout<<order[i]<<" ";
    } 
    cout<<endl; 
}

//随机排序 
void knapsack_random()
{
   int i,j;
    int temporder = 0;
    double temp = 0;
    for(i=1;i<=n;i++) {
         //   int j = parseInt(Math.random() * (n - 1));
         	srand((unsigned)time(NULL)); /*播种子,这里用到了time需要包含头文件time.h*/
            int j =rand()%n+1;//rand()%n生成0~（n-1）之间随机整数 
            temporder=order[i];//对order[]随机改变顺序
            order[i]=order[j];
            order[j]=temporder;
 
            temp = v[i];//相应对v[]改变顺序 
            v[i]=v[j];
            v[j]=temp;
 
            temp=w[i];//相应对w[]改变顺序
            w[i]=w[j];
            w[j]=temp;
        }
    cout<<"随机排序后顺序："<<endl;
       for(i=1;i<=n;i++)
    {
            cout<<order[i]<<" ";
    } 
    cout<<endl;
  
}
 
//回溯函数
void backtrack(int i)
{   //i用来指示到达的层数（第几步，从0开始），同时也指示当前选择玩了几个物品
    double bound(int i);
    if(i>n) //递归结束的判定条件
    {
    	for(int i = 1; i<= n; i++)
            best_x[i] = x[i];   //记录回溯的最优情况
        bestp = cp;
        return;
    }
    
    //如若左子节点可行，则直接搜索左子树;
    if(cw+w[i]<=c)//将物品i放入背包,搜索左子树
    {fluet++;
        cw+=w[i];//同步更新当前背包的重量
        cp+=v[i];//同步更新当前背包的总价值
        x[i]=1;
        backtrack(i+1);//深度搜索进入下一层
        cw-=w[i];//回溯复原
        cp-=v[i];//回溯复原
        x[i]=0;
    }
    //对于右子树，先计算上界函数，以判断是否将其减去
    if(bound(i+1)>bestp)//如若符合条件则搜索右子树
       {
	   fluet++;
	   x[i]=0;
	   backtrack(i+1);
		} 

	 
}
 
//计算上界函数，功能为剪枝
double bound(int i)
{   //判断当前背包的总价值cp＋剩余容量可容纳的最大价值<=当前最优价值
    double leftw= c-cw;//剩余背包容量
    double b = cp;//记录当前背包的总价值cp,最后求上界
    //以物品单位重量价值递减次序装入物品
    while(i<=n && w[i]<=leftw)
    {
        leftw-=w[i];
        b+=v[i];
        i++;
    }
    //装满背包
    if(i<=n)
        b+=v[i]/w[i]*leftw;
    return b;//返回计算出的上界
 
}
 
 
 
int main()
{
    int i;
 	for(i=1;i<=n;i++){
        order[i]=i;
    }
    
     // 按 v/w 降序排列访问
    cout<<"按 v/w 降序排列的算法访问: "<<endl; 
    knapsack();
    backtrack(1);
    cout<<"最优价值为："<<bestp<<endl;
    cout<<"需要装入的物品编号是：";
    for(i=1;i<=n;i++)
    {
        if(best_x[i]==1)
            cout<<order[i]<<" ";
    }
    cout<<endl;
    cout<<"访问节点数："<< fluet<<endl;

    //随机访问 
    fluet=0;
     cout<<"按随机序列的算法访问: "<<endl;
    knapsack_random();
    backtrack(1);
    cout<<"最优价值为："<<bestp<<endl;
    cout<<"需要装入的物品编号是：";
    for(i=1;i<=n;i++)
    {
        if(best_x[i]==1)
            cout<<order[i]<<" ";
    }
    cout<<endl;
    cout<<"访问节点数："<< fluet<<endl; 
    
    return 0;
}
           

数据输出：

结果分析：

从这个数据结果输出来看，按 v/w 降序排列的算法访问的程序代码是没有问题的。（网上的回溯法我看实质上都是结合贪心做的）。但是很明显可以看到在按随机算法访问序列那里，程序输出的结果并不准确。个人分析原因是因为在随机序列算法访问节点时，未对程序进行排序，则计算bound（）函数并未算对，导致右子树的剪枝不正确。

不太知道怎么改，有没有大神帮忙修改一下~