92. 背包问题
2019-05-18 本文已影响0人
薄荷糖的味道_fb40
描述
在n个物品中挑选若干物品装入背包,最多能装多满?假设背包的大小为m,每个物品的大小为A[i]。
样例
样例 1:
输入: [3,4,8,5], backpack size=10
输出: 9
样例 2:
输入: [2,3,5,7], backpack size=12
输出: 12
思路:
设为前个物品是否能拼成重量。则取决于两种情况:
1.前个物品能够拼成重量。
2.前个物品能够拼成重量。
具体实现如下。
class Solution {
public:
/**
* @param m: An integer m denotes the size of a backpack
* @param A: Given n items with size A[i]
* @return: The maximum size
*/
int backPack(int m, vector<int> &A) {
// write your code here
int n=A.size();
if(!n)
{
return 0;
}
vector<vector<bool>> dp(n+1,vector<bool>(m+1,false));
for(int i=0;i<=n;i++)
{
dp[i][0]=true;
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
dp[i][j]=dp[i-1][j];
if(j-A[i-1]>=0)
{
dp[i][j]=dp[i][j]||dp[i-1][j-A[i-1]];
}
}
}
for(int i=m;i>=0;i--)
{
if(dp[n][i])
{
return i;
}
}
return 0;
}
};