小心下标对应不一致带来的问题。小心。
zero_one_pack(v[i],c[i]) for j = M to c[i] f[j] = max( f[j-c[i]]+v[i] , f[j] )f[0......M] = 0; // 初始化第0行，即一个物品都没有的情形。J一定要包括0.这是关键。for i = 1 to N zero_one_pack(v[i],w[i])下面的代码i可以从0开始，因为二维数组的时候，i=0开始要存储0个物品的情形。此时，不需要。因为上一行已经存了。我还是保留了i=1开始的情形，小心物品下标即可。
class Solution {public: /** * @param m: An integer m denotes the size of a backpack * @param A: Given n items with size A[i] * @return: The maximum size */ int backPack(int m, vector<int> A) { // write your code here vector<int> f(m+1, 0); int n = A.size(); for(int i = 1; i <= n; ++i){ for(int j = m; j >= A[i-1]; --j){ f[j] = max( f[j], f[j-A[i-1]] + A[i-1] ); } } return f[m]; }};新闻热点
疑难解答
