蛮力法、动态规划法、回溯法和分支限界法求解(11)

xnode = x.p;

}

v = xnode->p;

for( i=0; i<n; i++){ //取装入背包中物体在排序前的序号

if(xnode->s1[i]){

X[a[i].sign] =1 ;

}else{

X[a[i].sign] = 0;

}

}

delete xnode;

delete heap;

return v; //返回背包中物体的价值

}

/*测试以上算法的主函数*/

int main()

{

goods b[N];

printf("物品种数n: ");

scanf("%d",&n); //输入物品种数

printf("背包容量C: ");

scanf("%d",&C); //输入背包容量

for (int i=0;i<n;i++) //输入物品i的重量w及其价值v

{

printf("物品%d的重量w[%d]及其价值v[%d]:

",i+1,i+1,i+1);

scanf("%d%d",&a[i].w,&a[i].p);

b[i]=a[i];

}

int sum4=KnapSack4(n,a,C,X);//调用分支限界法求0/1背包问题

printf("分支限界法求解0/1背包问题:\nX=[ ");

for(i=0;i<n;i++)

cout<<X[i]<<" ";//输出所求X[n]矩阵

printf("] 装入总价值%d\n",sum4);

return 0;

}

3)复杂度分析：

分支限界法求解0/1背包问题的时间复杂度为：T(n) O(2n)。

相同的数据，求相同同的问题，用不同的方法，得到的结果，所得结果 正式所求问题的最优解，所编程序是正确的。

五、调试和运行程序过程中产生的问题、采取的措施及获得的相关经验教训：

1.本实验中4种算法要用同一个主函数调用，由于背包容量、物品、解向量

等变量都是以全局变量定义的，每次调用一种算法之前，必须要看这些重要的变