给出 n 个物品, 以及一个数组, nums[i] 代表第i个物品的大小, 保证大小均为正数, 正整数 target 表示背包的大小, 找到能填满背包的方案数。
每一个物品只能使用一次

在线评测地址：领扣题库官网

样例

给出候选物品集合 [1,2,3,3,7] 以及 target 7
结果的集合为:
[7]
[1,3,3]
返回 2

算法：DP(动态规划)

题目描述
nums[i]表示第i个物品的大小 ；target 表示背包的大小；每个物品只能使用一次；求装满背包的方案数。
算法思路

• 题目说物品只能使用一次和求方案数，可以看出这题的模型是01背包
• 我们定义状态dpi 来表示前i个物品重量有多少种方式组出重量j
• 状态转移方程为：
  当不放第i个物品时 ： dpi = dpi - 1

当放第i个物品时：dpi += dpi - 1]

代码思路

1. 当没有物品时直接 return false
2. 定义一个二维数组dp[i][j]来表示前i个物品重量有多少种方式组出重量j
3. 两层循环嵌套来实现
4. 第一层循环枚举i表示前i个物品的重量
5. 第二层循环枚举j表示重量
6. 根据算法思路中的状态转移方程来实现
7. dp[n][target]方案数
8. return dp[n][target]

复杂度分析

• 空间复杂度：O(N*target)
• 时间复杂度：O(N*target)
  优化
• 我们可以利用滚动数组将状态定义成一维数组,dp[j]表示组成重量j的方案
• 下面是优化的核心部分的伪代码

for i 1 to n

 old = now; 
 now = 1 + now;
 for j 0 to target 
     dp[now][j] = dp[old][j]
     if (j >= nums[i - 1])
         dp[now][j] += dp[old][j - nums[i - 1]];

原本是 老值 + 老值 = 新值，如果正着更新，可能会出现 老值 + 新值，所以需要倒着更新。dpi = dpi-1 + dpi-1]，新值 = 两个老值加起来

for i 1 to n

 for j target to 0
         if (j >= nums[i - 1])
                 // old + old ==> new 
                 // old1 = dp[j]
                 // old2 = dp[j - nums[i - 1]]
                 dp[j] += dp[j - nums[i - 1]];

优化后复杂度分析

• 空间复杂度：O(target)
• 时间复杂度：O(N*target)

public class Solution {

    /**
     * @param nums: an integer array and all positive numbers
     * @param target: An integer
     * @return: An integer
     */
    public int backPackV(int[] nums, int target) {
        // write your code here
        int n = nums.length;
        // 当没有物品时方案数为0
        if (n == 0) {
            return 0;
        }
        // dp[i][j]表示前i个数字有多少种方式拼出数字j
        int[][] dp = new int[n + 2][target + 2];    
        // 初始化dp[i][j]
        for (int i = 0; i <= target; i++) {
            if(i == 0) {
                dp[0][i] = 1;
            }
            else {
                dp[0][i] = 0;
            }
        }
        for (int i = 1; i <= n; i++) {
            // 装入的重量
            for (int j = 0; j <= target; j++) {
                // 不放物品
                dp[i][j] = dp[i - 1][j];
                // 放入物品

                if (j >= nums[i - 1]) {     
                    dp[i][j] += dp[i - 1][j - nums[i - 1]];
                }
            }
        }
        return dp[n][target];
    }
}

更多题解参考：九章官网solution