描述
在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;
}
};
