给出 n 个物品, 以及一个数组, nums[i] 代表第i个物品的大小, 保证大小均为正数, 正整数 target 表示背包的大小, 找到能填满背包的方案数。 每一个物品只能使用一次
样例 给出候选物品集合 [1,2,3,3,7] 以及 target 7
结果的集合为: [7] [1,3,3] 返回 2
思路：本题是昨天背包问题的变种，这里求的是能装进背包的种数了。
分析都差不多，变化主要在：
f[i][w]变成前i个物品有多少种方式拼出重量w转移方程为： 代码实现：(未优化空间版) class Solution { public: /** * @param nums: an integer array and all positive numbers * @param target: An integer * @return: An integer */ int backPackV(vector<int> &nums, int target) { int n = nums.size(); if(n == 0) return 0;//0个物品拼出重量0 vector<vector<int>> f(n + 1,vector<int>(target + 1,0)); f[0][0] = 1;//前0个物品有一种方式拼出重量0（主要是为了计算方便） for(int i = 1;i <= n;++i) { for(int j = 0;j <= target;++j) { if(j >= nums[i - 1])//当前剩余重量要大于等于当前将要放入物品的重量 { f[i][j] = f[i - 1][j] + f[i - 1][j - nums[i - 1]]; } else//如果剩余重量已经小于当前物品重量 则只能使用前一次的值 { f[i][j] = f[i - 1][j]; } } } return f[n][target]; } };思路二：观察可以发现，我们在使用f数组时，更新数据的时候值跟前一行的数据有关，如果我们直接从后面向前面遍历j的话，就可以只需要一个大小为target的数组就可以了。
代码如下：
class Solution { public: /** * @param nums: an integer array and all positive numbers * @param target: An integer * @return: An integer */ int backPackV(vector<int> &nums, int target) { int n = nums.size(); if(n == 0) return 0;//0个物品拼出重量0 vector<int> f(target + 1,0); f[0] = 1;//前0个物品有一种方式拼出重量0 //要反向来求 如果使用优化空间的话 for(int i = 1;i <= n;++i) { for(int j = target;j >= 0;--j) { if(j >= nums[i-1]) { //old + old = new f[j] = f[j] + f[j-nums[i - 1]]; } else { f[j] = f[j];//否则就是当前值 } } } return f[target]; } };