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

}

return bestP;

}

cw=cw+a[i].w;

cp=cp+a[i].p;

cx[i]=1; //装入背包

Force(i+1);

cw=cw-a[i].w;

cp=cp-a[i].p;

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

Force(i+1);

return bestP;

}

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

{

Force(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 sum1=KnapSack1(n,a,C,X);//调用蛮力法求0/1背包问题

printf("蛮力法求解0/1背包问题:\nX=[ ");

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

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

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

bestP=0,cp=0,cw=0;//恢复初始化

}

3）复杂度分析：

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

2.动态规划法求解0/1背包问题：

1）基本思想：