g**********y
发帖数: 14569 | 1 Given a number N, print all the ways (combinations) to represent the number
from the given set of integers.
Ex: Given set is {2,3,7,8,9} and given number N = 7, then the combinations
are:
7,2+2+3. Repetitions are not allowed, hence 3+2+2 or 2+3+2 are not allowed.
是个典型的递归搜索。
面试的人问他能不能O(n^2)或者O(n^3), 这个不可能吧？允许一个数重复用的话，答案
就是指数级的。
有什么想法？ |
d*****o
发帖数: 28 | 2 use DP.
sort the array first, then use two dimensional array
a[k][N] to calculate the result.
k -- the length of the set (k is 5 in the example)
N -- target value (N is 7 in the example)
The complexity is O(K*N) |
M**u
发帖数: 10158 | 3 how about:
{2, 3, 4, 6} to get N=8
when k=3, you can have {2,3,3}, {2,2,4}
【在 d*****o 的大作中提到】
: use DP.
: sort the array first, then use two dimensional array
: a[k][N] to calculate the result.
: k -- the length of the set (k is 5 in the example)
: N -- target value (N is 7 in the example)
: The complexity is O(K*N)
|
g***s
发帖数: 3811 | |
g**********y
发帖数: 14569 | 5 完全背包问题，是求一个解，这个我相信可以O(kN)解。
A的问题是列出所有解。所有解本身是指数级，怎么可能在O(kN)算得出来呢？ |
c****p
发帖数: 6474 | 6 因为解集随着递规深度的增加坍缩得很快吧？
【在 g**********y 的大作中提到】
: 完全背包问题，是求一个解，这个我相信可以O(kN)解。
: A的问题是列出所有解。所有解本身是指数级，怎么可能在O(kN)算得出来呢？
|
g**********y
发帖数: 14569 | 7 对{2, 3, 5, 7, 11, 13}， N=100, 有6898种解。
把解集打印出来就已经不可能k*N级别的了。
【在 c****p 的大作中提到】
: 因为解集随着递规深度的增加坍缩得很快吧？
|
g***s
发帖数: 3811 | 8 前面用DP建立状态数组，打印结果的时候递归求解。但因为状态数组已经建立，所以递
归的时候不会访
问到任何无效结果。复杂度和结果数目也有关系。
【在 g**********y 的大作中提到】
: 完全背包问题，是求一个解，这个我相信可以O(kN)解。
: A的问题是列出所有解。所有解本身是指数级，怎么可能在O(kN)算得出来呢？
|
f****4
发帖数: 1359 | 9 你这的2可以取两次？
可能的combinations是
2,3,7,23
还是，我理解错了？
谢谢
number
【在 g**********y 的大作中提到】
: Given a number N, print all the ways (combinations) to represent the number
: from the given set of integers.
: Ex: Given set is {2,3,7,8,9} and given number N = 7, then the combinations
: are:
: 7,2+2+3. Repetitions are not allowed, hence 3+2+2 or 2+3+2 are not allowed.
: 是个典型的递归搜索。
: 面试的人问他能不能O(n^2)或者O(n^3), 这个不可能吧？允许一个数重复用的话，答案
: 就是指数级的。
: 有什么想法？
|
d*****o
发帖数: 28 | 10 Are you sure there are 6898?
I got 1141.
I verified it works for small N and K but did not verify it for 6898
Here is my code (in java) |
|
|
d*****o
发帖数: 28 | 11 Code correction:
public static int findWays(int[] a, int target)
{
int K = a.length;
int N = target;
int[][] DP = new int[K][N];
for(int i=0; i < K; i++)
for(int j = 0; j < N; j++)
DP[i][j] = 0;
for(int i = 0; i < K; i++)
DP[i][0] = 1;
for(int i=0; i < K; i++)
for(int j = 0; j < N; j++)
{
if(i>=1)
DP[i][j] += DP[i-1][j];
if(j-a[i] >= 0)
DP[i][j] += DP[i][j-a[i]];
}
return DP[K-1][N-1];
} |
g**e
发帖数: 6127 | 12 try a={2}, target=1 or 2
【在 d*****o 的大作中提到】
: Code correction:
:
: public static int findWays(int[] a, int target)
: {
: int K = a.length;
: int N = target;
: int[][] DP = new int[K][N];
: for(int i=0; i < K; i++)
: for(int j = 0; j < N; j++)
: DP[i][j] = 0;
|
d*******d
发帖数: 2050 | 13 可dp和recursive都没解决重复问题阿？
【在 g**********y 的大作中提到】
: Given a number N, print all the ways (combinations) to represent the number
: from the given set of integers.
: Ex: Given set is {2,3,7,8,9} and given number N = 7, then the combinations
: are:
: 7,2+2+3. Repetitions are not allowed, hence 3+2+2 or 2+3+2 are not allowed.
: 是个典型的递归搜索。
: 面试的人问他能不能O(n^2)或者O(n^3), 这个不可能吧？允许一个数重复用的话，答案
: 就是指数级的。
: 有什么想法？
|
g**********y
发帖数: 14569 | 14 public class SplitNumber {
private int count;
public int countWays(int sum, int[] numbers) {
int N = sum/numbers[0] + 1;
int[] a = new int[N];
count = 0;
for (int i=0; i
a[0] = numbers[i];
split(sum, numbers, a, i, 1, a[0]);
}
return count;
}
private void split(int sum, int[] numbers, int[] a, int low, int len,
int curSum) {
if (curSum == sum) {
count++;
for (int i=0; i
System.out.print(a[i] + " ");
}
System.out.println();
return;
}
for (int i=low; i
if (curSum + numbers[i] > sum) break;
a[len] = numbers[i];
split(sum, numbers, a, i, len+1, curSum+numbers[i]);
}
}
}
【在 d*******d 的大作中提到】
: 可dp和recursive都没解决重复问题阿？
|
g**********y
发帖数: 14569 | 15 I am not 100% sure, but from print out result, it looks right.
Code is posted, print out is in sorted order.
【在 d*****o 的大作中提到】
: Are you sure there are 6898?
: I got 1141.
: I verified it works for small N and K but did not verify it for 6898
: Here is my code (in java)
|
d*****o
发帖数: 28 | 16
【在 g**e 的大作中提到】
: try a={2}, target=1 or 2
|
d*****o
发帖数: 28 | 17 Sorry,
Your code is correct, my code has got more results and there are some
duplicates.
【在 g**********y 的大作中提到】
: I am not 100% sure, but from print out result, it looks right.
: Code is posted, print out is in sorted order.
|
d*******d
发帖数: 2050 | 18 yeah, 我想出来了。
不过dp要记下每一步的解，也够麻烦的。
【在 g**********y 的大作中提到】
: public class SplitNumber {
: private int count;
:
: public int countWays(int sum, int[] numbers) {
: int N = sum/numbers[0] + 1;
: int[] a = new int[N];
: count = 0;
: for (int i=0; i: a[0] = numbers[i];
: split(sum, numbers, a, i, 1, a[0]);
|
n**z
发帖数: 155 | 19 if(i>=1)
DP[i][j] += DP[i-1][j];
if(j-a[i] >= 0)
DP[i][j] += DP[i][j-a[i]];
DP 不大熟悉。能解释以下这几行吗 THANKS. |
g***s
发帖数: 3811 | 20 他的代码有点小错误，应该是：
public static int findWays(int[] a, int target) {
int K = a.length;
int N = target;
int[][] DP = new int[K][N+1];
DP[0][0] = 1;
for (int i = 0; i < K; i++)
for (int j = 0; j < N+1; j++) {
if (i >= 1)
DP[i][j] += DP[i - 1][j];
if (j - a[i] >= 0)
DP[i][j] += DP[i][j - a[i]];
}
return DP[K - 1][N];
}
【在 n**z 的大作中提到】
: if(i>=1)
: DP[i][j] += DP[i-1][j];
: if(j-a[i] >= 0)
: DP[i][j] += DP[i][j-a[i]];
: DP 不大熟悉。能解释以下这几行吗 THANKS.
|
|
|
g***s
发帖数: 3811 | 21 你的思路也是对的。有点小错误而已。
【在 d*****o 的大作中提到】
: Sorry,
: Your code is correct, my code has got more results and there are some
: duplicates.
|
s*****y
发帖数: 897 | 22 But still. How to print out the result from this DP table?
Thanks
【在 g***s 的大作中提到】
: 你的思路也是对的。有点小错误而已。
|
s*******d
发帖数: 4135 | 23 这个题跟careecup上那道找硬币组合的题实际上是一个意思。
【在 s*****y 的大作中提到】
: But still. How to print out the result from this DP table?
: Thanks
|
g***s
发帖数: 3811 | 24 递归。但有了这个DP table，所有的访问节点都是有效的。【 在 speeddy (Wade) 的
大作中提
到: 】 |
s*****y
发帖数: 897 | 25 Can you give out the link.
【在 s*******d 的大作中提到】
: 这个题跟careecup上那道找硬币组合的题实际上是一个意思。
|
s*******d
发帖数: 4135 | 26 你这个代码里面开始的时候，是不是要首先初始化dp数组全部为0，
然后将dp[0][0]=1这行换成下面的代码？
for (int i = 0; i < len; ++i)
{
if (a[i] <= target) dp[i][a[i]] = 1;
}
这样运行程序，按照前面的测试，出来的结果是6898
我怎么都想不明白你这个dp[0][0]=1是个啥意思? 请指教。
【在 g***s 的大作中提到】
: 他的代码有点小错误，应该是：
: public static int findWays(int[] a, int target) {
: int K = a.length;
: int N = target;
: int[][] DP = new int[K][N+1];
: DP[0][0] = 1;
: for (int i = 0; i < K; i++)
: for (int j = 0; j < N+1; j++) {
: if (i >= 1)
: DP[i][j] += DP[i - 1][j];
|
n**z
发帖数: 155 | 27 不对，那个数字代表已知的和为该j的组合。最初的时候只有和为零的有一种组合。
【在 s*******d 的大作中提到】
: 你这个代码里面开始的时候，是不是要首先初始化dp数组全部为0，
: 然后将dp[0][0]=1这行换成下面的代码？
: for (int i = 0; i < len; ++i)
: {
: if (a[i] <= target) dp[i][a[i]] = 1;
: }
: 这样运行程序，按照前面的测试，出来的结果是6898
: 我怎么都想不明白你这个dp[0][0]=1是个啥意思? 请指教。
|
g***s
发帖数: 3811 | 28 java默认0.
没必要改dp[0][0]=1就够了，这样出来的也就是6898.
这个表示只取第一个数字，和为0的数目，显然是1，就是一个不取。
【在 s*******d 的大作中提到】
: 你这个代码里面开始的时候，是不是要首先初始化dp数组全部为0，
: 然后将dp[0][0]=1这行换成下面的代码？
: for (int i = 0; i < len; ++i)
: {
: if (a[i] <= target) dp[i][a[i]] = 1;
: }
: 这样运行程序，按照前面的测试，出来的结果是6898
: 我怎么都想不明白你这个dp[0][0]=1是个啥意思? 请指教。
|
s*******d
发帖数: 4135 | 29 yes, you are right. Now I understand.
dp[i][j] means the number of ways to get the sum j using a[0]..a[i]
so for dp[0][0] is the number of ways to get the sum 0 using a[0],
which is 1 that picks up nothing.
【在 g***s 的大作中提到】
: java默认0.
: 没必要改dp[0][0]=1就够了，这样出来的也就是6898.
: 这个表示只取第一个数字，和为0的数目，显然是1，就是一个不取。
|
h***i
发帖数: 1970 | 30 set里面的数可以是负数。
【在 g***s 的大作中提到】
: 他的代码有点小错误，应该是：
: public static int findWays(int[] a, int target) {
: int K = a.length;
: int N = target;
: int[][] DP = new int[K][N+1];
: DP[0][0] = 1;
: for (int i = 0; i < K; i++)
: for (int j = 0; j < N+1; j++) {
: if (i >= 1)
: DP[i][j] += DP[i - 1][j];
|
|
|
g***s
发帖数: 3811 | 31 i dont think so. if there are negative numbers, there is unlimit output.
【在 h***i 的大作中提到】
: set里面的数可以是负数。
|
