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

if(j<a[i-1].w) V[i][j]=V[i-1][j]; else V[i][j]=max(V[i-1][j],V[i-1][j-a[i-1].w]+a[i-1].p); j=C; //求装入背包的物品 for (i=n;i>0;i--) { if (V[i][j]>V[i-1][j]){ x[i-1]=1; j=j-a[i-1].w; x[i-1]=0; } else } return V[n][C]; //返回背包取得的最大价值

}

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 sum2=KnapSack2(n,a,C,X);//调用动态规划法求0/1背包问题

printf("动态规划法求解0/1背包问题:\nX=[ ");

for(i=0;i<n;i++) cout<<X[i]<<" ";//输出所求X[n]矩阵 printf("] 装入总价值%d\n",sum2); for (i=0;i<n;i++) { a[i]=b[i]; }//恢复a[N]顺序

}

3）复杂度分析:

动态规划法求解0/1背包问题的时间复杂度为：T(n) O(n C)。

3.回溯法求解0/1背包问题：

1）基本思想：

回溯法：为了避免生成那些不可能产生最佳解的问题状态，要不断