有 n 个物品和一个大小为 m 的背包. 给定数组 A 表示每个物品的大小 数组 V 表示每个物品的价值.
问最多能装入背包的总价值是多大?
样例 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) 空间复杂度吗?
注意事项 A[i], V[i], n, m 均为整数 你不能将物品进行切分 你所挑选的要装入背包的物品的总大小不能超过 m 每个物品只能取一次
表示第i
件物品下,重量为 j
时的物品价值
dp[0][0] = 0, dp[0][A[0]] = V[0]
class Solution {
public:
int backPackII(int m, vector<int> &A, vector<int> &V) {
int n = A.size(), i, j;
vector<vector<int>> dp(n,vector<int>(m+1,-1));
dp[0][0] = 0, dp[0][A[0]] = V[0];
for(i = 1; i < n; ++i)
{
for(j = m; j >= 0; --j)
{
if(dp[i-1][j] != -1)//上一行存在的状态
{
dp[i][j] = dp[i-1][j];//不取物品
if(j+A[i] <= m)//取物品,且不超重
dp[i][j+A[i]] = max(dp[i][j+A[i]],dp[i-1][j]+V[i]);
}
}
}
return *max_element(dp[n-1].begin(),dp[n-1].end());
//取最大的方案
}
};
100% 数据通过测试 总耗时 50 ms 您的提交打败了 99.80% 的提交!