a****l
发帖数: 30 | 1 Given n items with size nums[i] which an integer array and all positive
numbers, no duplicates. An integer target denotes the size of a backpack.
Find the number of possible fill the backpack.
Each item may be chosen unlimited number of times
Example
Given candidate items [2,3,6,7] and target 7,
A solution set is:
[7]
[2, 2, 3]
return 2
class Solution {
public:
int backPackIV(vector& nums, int target) {
vector f(target + 1);
f[0] = 1;
// for (auto num : nums) {
// for (int i = 1; i <= target; ++i) {
// if (num <= i) f[i] += f[i-num];
// }
// }
// return f[target];
for (int i = 1; i <= target; ++i) {
for (auto num : nums) {
if (num <= i) f[i] += f[i-num];
}
}
return f[target];
}
};
注释掉的解法可以通过OJ,应该是正确的. 没注释掉的和注释掉的解法的不一样的地方
就是内外循环换了下, 求大神分析下为啥不行啊 | r******t
发帖数: 250 | 2 你拿小数据跑两趟就知道了
比如 target = 3，nums = ｛1， 2｝ | a*******g
发帖数: 1221 | 3 target = 5, nums = {2, 3}, 也就是item1的size = 2, item2的size = 3
结果应该是1，也就是{item1, item2}
而错的解法会返回2，多数了一种情况{item2, item1}，就是说错的解法会数重了，错
的解法没有考虑item之间的顺序。而正解的解法在递归时考虑到了item之间的顺序。 | m********6
发帖数: 58 | 4 I got asked this question by Facebook. The tricky part is permutation can
only be counted once. Here is my solution:
public int getCount(int[] partitions, int target)
{
int[][] dp = new int[target+1][partitions.length];
Arrays.fill(dp[0], 1);
for (int i = 1; i <= target; i++)
{
Arrays.fill(dp[i], -1);
}
return getCount(partitions, target, 0, dp);
}
public int getCount(int[] partitions, int target, int index, int[][] dp)
{
if (target < 0)
{
return 0;
}
if (dp[target][index] != -1)
{
return dp[target][index];
}
int count = 0;
for (int i = index; i < partitions.length; i++)
{
count += getCount([partitions, target - partitions[i], i, dp);
}
dp[target][index] = count;
return count;
} |
|
