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

令V(i,j)表示在前i(1 i n)个物品中能够装入容量为j(1 j C)的

背包中的物品的最大值，则可以得到如下动态函数：

V(i,0) V(0,j) 0

V(i 1,j)(j wi) V(i,j) V(i 1,j),V(i 1,j wi) vi (j wi) max

按照下述方法来划分阶段：第一阶段，只装入前1个物品，确定在

各种情况下的背包能够得到的最大价值；第二阶段，只装入前2个物品，

确定在各种情况下的背包能够得到的最大价值；以此类推，直到第n个

阶段。最后，V(n,C)便是在容量为C的背包中装入n个物品时取得的最

大价值。

2）代码：

#include<iostream>

#include<algorithm>

using namespace std;

#define N 100 //最多可能物体数

struct goods

{ //物品结构体

int sign; //物品序号

int w; //物品重量

int p; //物品价值

}a[N];

bool m(goods a,goods b)

{

return (a.p/a.w)>(b.p/b.w);

}

int max(int a,int b)

{

return a<b?b:a;

}

int n,C,bestP=0,cp=0,cw=0;

int X[N],cx[N];

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

{

int V[N][10*N]; for(int i=0;i<=n;i++) V[i][0]=0; for(int j=0;j<=C;j++) V[0][j]=0; for(i=1;i<=n;i++) for(j=1;j<=C;j++) //初始化第0列 //初始化第0行 //计算第i行，进行第i次迭代