博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
背包问题2 (lintcode)
阅读量:6819 次
发布时间:2019-06-26

本文共 1153 字,大约阅读时间需要 3 分钟。

这里:

for(int j = 1;j <= m;j++)

result[0][j] = 0x80000000;

不能从0开始,result[0][0]是可以取到的,是0。其他情况取不到才用最小表示。

class Solution {public:    /*     * @param m: An integer m denotes the size of a backpack     * @param A: Given n items with size A[i]     * @param V: Given n items with value V[i]     * @return: The maximum value     */    int backPackII(int m, vector
&A, vector
&V) { // write your code here int length = A.size(); vector
> result(length+1,vector
(m+1)); for(int i = 0;i <= length;i++) result[i][0] = 0; for(int j = 1;j <= m;j++) result[0][j] = 0x80000000; for(int i = 1;i <= length;i++){ for(int j = 1;j <= m;j++){ if((j - A[i-1]) >= 0) result[i][j] = max(result[i-1][j-A[i-1]] + V[i-1],result[i-1][j]); else result[i][j] = result[i-1][j]; } } int max = 0; for(int i = 1;i <= m;i++){ if(result[length][i] > max) max = result[length][i]; } return max; }};

 

转载地址:http://nvszl.baihongyu.com/

你可能感兴趣的文章