这是清华算法设计C++描述上的代码吧?呵呵 我正巧读过。
简单解释一下吧 在解释之前你要知道动态规划是一个自底向上的过程
这个算法用到了一个二维数组m[][] 来存储各个坐标的价值信息 所以横坐标表示背包号码 纵坐标表示背包容量从1到c
注意该算法只能限制c是整数且每个背包的重量也是整数.
然后int jMax=min(w[n]-1,c);找出w[n]-1和 c之间的小者。
for(int j=0;j<=jMax;j++) m[n][j]=0;表示第n个物品不选 那么所以价值为0
for(int j=w[n];j<=c;j++) m[n][j]=v[n];表示第n个物品选择 所以价值为v[n]
for(int i=n-1;i>1;i--){
jMax=min(w[i]-1,c);
for(int j=0;j<=jMax;j++) m[i][j]=m[i+1][j];
for(int j=w[i];j<=c;j++) m[i][j]=max(m[i+1][j],m[i+1][j-w[i]]+v[i]);
}
表示自n-1到2逐层计算各m[i][j]的值 每一个m[i][j]的值都是根据上一层也就是m[i][j+1] 得到的 最后处理个第一层的边界条件 m[1][c]就是所得答案了