描述
有 n 個物品和一個大小為 m 的背包. 給定數(shù)組 A 表示每個物品的大小和數(shù)組 V 表示每個物品的價值.
問最多能裝入背包的總價值是多大?
A[i], V[i], n, m 均為整數(shù)
你不能將物品進行切分
你所挑選的要裝入背包的物品的總大小不能超過 m
樣例
樣例 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
思路：
表示前
個物品拼成重量
的時候能獲得的最大價值糟需，可以得到遞推表達式：
考慮最后一個物品是否被裝入背包兩種情況。具體實現(xiàn)如下。
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();
if(!n)
{
return 0;
}
vector<vector<int>> dp(n+1,vector<int>(m+1,-1));
dp[0][0]=0;
int res=0;
for(int i=1;i<=n;i++)
{
for(int j=0;j<=m;j++)
{
dp[i][j]=dp[i-1][j];
if(j-A[i-1]>=0 && dp[i-1][j-A[i-1]]!=-1)
{
dp[i][j]=max(dp[i][j],dp[i-1][j-A[i-1]]+V[i-1]);
}
res=max(res,dp[i][j]);
}
}
return res;
}
};
