描述
给出 n 个物品, 以及一个数组, nums[i] 代表第i个物品的大小, 保证大小均为正数, 正整数 target 表示背包的大小, 找到能填满背包的方案数。
每一个物品只能使用一次
样例
给出候选物品集合 [1,2,3,3,7] 以及 target 7
结果的集合为:
[7]
[1,3,3]
返回 2
思路：
这题和92. 背包问题很类似，只需要把设置成前
个物品拼成
的重量的方案数并且把||换成+就好了。具体实现如下。
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) {
// write your code here
int n=nums.size();
vector<vector<int>> dp(n+1,vector<int>(target+1,0));
for(int i=0;i<=n;i++)
{
dp[i][0]=1;
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=target;j++)
{
dp[i][j]=dp[i-1][j];
if(j-nums[i-1]>=0)
{
dp[i][j]+=dp[i-1][j-nums[i-1]];
}
}
}
return dp[n][target];
}
};
