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

}

cx[a[i].sign]=0; //不装入背包

BackTrack(i+1);

return bestP;

}

int KnapSack3(int n,goods a[],int C,int x[])

{

for(int i=0;i<n;i++) { x[i]=0; a[i].sign=i; } sort(a,a+n,m);//将各物品按单位重量价值降序排列 BackTrack(0);

return bestP;

}

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 sum3=KnapSack3(n,a,C,X);//调用回溯法求0/1背包问题

printf("回溯法求解0/1背包问题:\nX=[ "); for(i=0;i<n;i++) cout<<X[i]<<" ";//输出所求X[n]矩阵 printf("] 装入总价值%d\n",sum3); for (i=0;i<n;i++) { a[i]=b[i]; }//恢复a[N]顺序

3）复杂度分析：

最不理想的情况下，回溯法求解0/1背包问题的时间复杂度为：

T(n) O(2n)。由于其对蛮力法进行优化后的算法，其复杂度一般比蛮力

法要小。

空间复杂度：有n个物品，即最多递归n层，存储物品信息就是一个