lintcode 125 · 背包问题（二）

描述

有 n 个物品和一个大小为 m 的背包. 给定数组 A 表示每个物品的大小和数组 V 表示每个物品的价值.

问最多能装入背包的总价值是多大?

1. A[i], V[i], n, m 均为整数
2. 你不能将物品进行切分
3. 你所挑选的要装入背包的物品的总大小不能超过 m
4. 每个物品只能取一次
5. m <= 1000m<=1000\

len(A),len(V)<=100len(A),len(V)<=100

样例

样例 1：

输入：

m = 10
A = [2, 3, 5, 7]
V = [1, 5, 2, 4]

输出：

9

解释：

装入 A[1] 和 A[3] 可以得到最大价值, V[1] + V[3] = 9

样例 2：

输入：

m = 10
A = [2, 3, 8]
V = [2, 5, 8]

输出：

10

解释：

装入 A[0] 和 A[2] 可以得到最大价值, V[0] + V[2] = 10

挑战

O(nm) 空间复杂度可以通过, 你能把空间复杂度优化为O(m)吗？

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<int> &a, vector<int> &v) {
        // write your code here
        int n=a.size();
        vectorint>>temp(n+1,vector<int>(m+1,0));
        for(int i=1;i1;i++){
            for(int j=1;j1;j++){
                temp[i][j]=a[i-1]>j ? temp[i-1][j] : max(temp[i-1][j],temp[i-1][j-a[i-1]]+v[i-1]);
            }
        }
        return temp[n][m];
    }
};

动态规划