描述

在n個物品中挑選若干物品裝入背包，最多能裝多滿？假設(shè)背包的大小為m，每個物品的大小為A[i]。

樣例

樣例 1:
    輸入:  [3,4,8,5], backpack size=10
    輸出:  9

樣例 2:
    輸入:  [2,3,5,7], backpack size=12
    輸出:  12

思路：

設(shè)為前個物品是否能拼成重量。則取決于兩種情況：
1.前個物品能夠拼成重量。
2.前個物品能夠拼成重量。
具體實現(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]
     * @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;
    }
};