给出 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
