描述

有 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 hereint n=a.size();vector<vector<int>>temp(n+1,vector<int>(m+1,0));for(int i=1;i<n+1;i++){for(int j=1;j<m+1;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];}
};

动态规划