a***o
发帖数: 24 | 1 Suppose you are given a function void NumberofSum(int n) , write a code such
that will print all the numbers that will sum up to n.
Input n Output
1 {1}
2 {(1,1),(2)}
3 {(1,1,1),(1,2),(3)}
4 {(1,1,1,1),(1,1,2),(1,3),(2,2),(4)}
感觉上应该用DP，可是又没啥思路。请各位大侠不吝赐教！谢谢！ | l*********r
发帖数: 674 | 2 不用DP吧：
假设下标从1开始：
set[1] = 1;
set[i] = {i, set[i-1] X set[1], set[i-2] X set[2], ... ，set[i/2 -1] X set[i/2+1] }
X 是Cartesian product. 结果要remove duplicate。
such
【在 a***o 的大作中提到】
: Suppose you are given a function void NumberofSum(int n) , write a code such
: that will print all the numbers that will sum up to n.
: Input n Output
: 1 {1}
: 2 {(1,1),(2)}
: 3 {(1,1,1),(1,2),(3)}
: 4 {(1,1,1,1),(1,1,2),(1,3),(2,2),(4)}
: 感觉上应该用DP，可是又没啥思路。请各位大侠不吝赐教！谢谢！
| a***o
发帖数: 24 | 3 我的思路也是类似，就是 set(4)={set(3)+1}U{set(2)+2}U{set(1)+3} (U是并集的意
思)， 然后remove duplicate。 不过这样复杂很高的说。 不知道有没有啥高效的方法
。 | Z*****Z
发帖数: 723 | 4 回溯
【在 a***o 的大作中提到】
: 我的思路也是类似，就是 set(4)={set(3)+1}U{set(2)+2}U{set(1)+3} (U是并集的意
: 思)， 然后remove duplicate。 不过这样复杂很高的说。 不知道有没有啥高效的方法
: 。
| a***o
发帖数: 24 | 5 大侠，可以详细讲一下吗？谢谢！
【在 Z*****Z 的大作中提到】
: 回溯
| Z*****Z
发帖数: 723 | 6 你告诉我你会做马踏棋盘和穷举排列组合，我就给你讲这个:)
【在 a***o 的大作中提到】
: 大侠，可以详细讲一下吗？谢谢！
| d******a
发帖数: 238 | 7 以前想过这道题，主要就是用递归吧。假设数组index放结果，首先就是选一个值为
index[0]，剩下的index[1]到index[n]小于等于这个值,递归的时候index[0] >= index
[1] >= index[2] >= ... >= index[n].
void sum_helper(int *a, int index, int n, int max)
{
int i;
if(n == 0)
{
for(i = 0; i < index; i++)
printf("%d ", a[i]);
printf("\n");
return;
}
for(i = 1; i <= max && i <= n; i++)
{
a[index] = i;
sum_helper(a, index + 1, n - i, i);
}
}
void sum(int n)
{
int *a = (int *)malloc(sizeof(int) * n);
int max;
for(max = 1; max <= n; max++)
{
a[0] = max;
sum_helper(a, 1, n - max, max);
}
}
such
【在 a***o 的大作中提到】
: Suppose you are given a function void NumberofSum(int n) , write a code such
: that will print all the numbers that will sum up to n.
: Input n Output
: 1 {1}
: 2 {(1,1),(2)}
: 3 {(1,1,1),(1,2),(3)}
: 4 {(1,1,1,1),(1,1,2),(1,3),(2,2),(4)}
: 感觉上应该用DP，可是又没啥思路。请各位大侠不吝赐教！谢谢！
| i**********e
发帖数: 1145 | 8 subset sum 的一个变种。
一些常见面试题的答案与总结 -
http://www.ihas1337code.com
such
【在 a***o 的大作中提到】
: Suppose you are given a function void NumberofSum(int n) , write a code such
: that will print all the numbers that will sum up to n.
: Input n Output
: 1 {1}
: 2 {(1,1),(2)}
: 3 {(1,1,1),(1,2),(3)}
: 4 {(1,1,1,1),(1,1,2),(1,3),(2,2),(4)}
: 感觉上应该用DP，可是又没啥思路。请各位大侠不吝赐教！谢谢！
| x*********s
发帖数: 2604 | 9 void numberOfSum(int sum, vector v, int last)
{
if(sum == 0)
{
for (int i = 0; i < v.size(); i++)
{
cout<
}
cout<
return;
}
for (int i = 1; i <= sum; i++)
{
if(sum - i >= 0 && i >= last)
{
vector temp = v;
temp.push_back(i);
numberOfSum(sum-i,temp,i);
}
}
} | a***o
发帖数: 24 | 10 谢谢，有思路了～
【在 i**********e 的大作中提到】
: subset sum 的一个变种。
: 一些常见面试题的答案与总结 -
: http://www.ihas1337code.com
:
: such
| | | A**l
发帖数: 2650 | 11 递归
F(n)
{
for(i=1; i
output(i, F(n-i));
}
当然还需要考虑重复的输出
such
【在 a***o 的大作中提到】
: Suppose you are given a function void NumberofSum(int n) , write a code such
: that will print all the numbers that will sum up to n.
: Input n Output
: 1 {1}
: 2 {(1,1),(2)}
: 3 {(1,1,1),(1,2),(3)}
: 4 {(1,1,1,1),(1,1,2),(1,3),(2,2),(4)}
: 感觉上应该用DP，可是又没啥思路。请各位大侠不吝赐教！谢谢！
| s*********l
发帖数: 103 | 12 http://spellscroll.com/questionfull/291/
http://en.wikipedia.org/wiki/Integer_partition
http://code.activestate.com/recipes/218332-generator-for-intege
http://www.cs.sunysb.edu/~algorith/files/generating-partitions.
such
【在 a***o 的大作中提到】
: Suppose you are given a function void NumberofSum(int n) , write a code such
: that will print all the numbers that will sum up to n.
: Input n Output
: 1 {1}
: 2 {(1,1),(2)}
: 3 {(1,1,1),(1,2),(3)}
: 4 {(1,1,1,1),(1,1,2),(1,3),(2,2),(4)}
: 感觉上应该用DP，可是又没啥思路。请各位大侠不吝赐教！谢谢！
| P******x
发帖数: 259 | 13 递归啊
such
【在 a***o 的大作中提到】
: Suppose you are given a function void NumberofSum(int n) , write a code such
: that will print all the numbers that will sum up to n.
: Input n Output
: 1 {1}
: 2 {(1,1),(2)}
: 3 {(1,1,1),(1,2),(3)}
: 4 {(1,1,1,1),(1,1,2),(1,3),(2,2),(4)}
: 感觉上应该用DP，可是又没啥思路。请各位大侠不吝赐教！谢谢！
| z*s
发帖数: 209 | 14 同意。
【在 i**********e 的大作中提到】
: subset sum 的一个变种。
: 一些常见面试题的答案与总结 -
: http://www.ihas1337code.com
:
: such
| a***o
发帖数: 24 | 15 Thank you all. Really very helpful suggestions. | b*****e
发帖数: 474 | 16 思路是对的，就是用递归，多用个参数，就是最大的数/上限，
n_series_with_upperbound(n,k)
= UNION ( n_series_with_max(n,j) ), j=1,2,...k
n_series_with_max(n,j)
= (list j n_series_with_upbound(n-j,j)) if n>=j; EMPTY otherwise
n_series = n_series_with_upperbound(n,n).
such
【在 a***o 的大作中提到】
: Suppose you are given a function void NumberofSum(int n) , write a code such
: that will print all the numbers that will sum up to n.
: Input n Output
: 1 {1}
: 2 {(1,1),(2)}
: 3 {(1,1,1),(1,2),(3)}
: 4 {(1,1,1,1),(1,1,2),(1,3),(2,2),(4)}
: 感觉上应该用DP，可是又没啥思路。请各位大侠不吝赐教！谢谢！
| f*******4
发帖数: 1401 | 17 用DP可以解吗？用subset sum的方法一个一个解？ | g*******s
发帖数: 490 | 18 DP就是从sum(n-1)推到sum(n),对于sum(n-1)的每个解，要不然在这个解中加一个
element 1,要不把这个解中现有的each element + 1，然后trim下，去掉duplicate就
可以了 | k***s
发帖数: 277 | 19 受到wiki上的启发， http://en.wikipedia.org/wiki/Integer_partition
wiki上是用smallest addedn is k, 我改成with m's largest addend k
// k is the maximum number of integer partition;
// m is the num of k of integer partition.
void ip_helper(int n, int k, int m, std::deque sequence) {
if (n < k*m)
return;
if (k < 1)
return;
int i, j, r = n-k*m;
for (i=0; i
sequence.push_back(k);
if (r == 0) {
for (i=0; i<(int)sequence.size(); ++i)
std::cout << sequence[i] << ' ';
std::cout << std::end;
return;
}
for (i=k-1; i>0; --i)
for (j=r/i; j>0; --j) {
ip_helper(r, i, j, sequence);
}
}
void ip(int n) {
std::cout << "integer partition for : " << n << std::endl;
int k,m;
std::deque sequence;
for (k=n; k>0; --k)
for (m=n/k; m>0; --m)
ip_helper(n, k, m, sequence);
}
【在 g*******s 的大作中提到】
: DP就是从sum(n-1)推到sum(n),对于sum(n-1)的每个解，要不然在这个解中加一个
: element 1,要不把这个解中现有的each element + 1，然后trim下，去掉duplicate就
: 可以了
| c******n
发帖数: 4965 | 20 就是coin 问题， coin set 从1,2,3,.... 一直到n
code such
【在 a***o 的大作中提到】
: Suppose you are given a function void NumberofSum(int n) , write a code such
: that will print all the numbers that will sum up to n.
: Input n Output
: 1 {1}
: 2 {(1,1),(2)}
: 3 {(1,1,1),(1,2),(3)}
: 4 {(1,1,1,1),(1,1,2),(1,3),(2,2),(4)}
: 感觉上应该用DP，可是又没啥思路。请各位大侠不吝赐教！谢谢！
| c******n
发帖数: 4965 | 21 find_sum( total , remaining_coin_set, used_coin_set ) {
if ( total == 0 ) {
print_out(used_coin_set);
}
else {
use_this_coin = remaining_coin_set.pop();
more_used_coin_set = { used_coin_set }
for( sub_total = total; sub_total >= 0; sub_total -=
use_this_coin.value() ) {
find_sum( sub_total, remaining_coin_set, more_used_coin_set);
more_used_coin_set.add(use_this_coin);
}
}
code such
【在 a***o 的大作中提到】
: Suppose you are given a function void NumberofSum(int n) , write a code such
: that will print all the numbers that will sum up to n.
: Input n Output
: 1 {1}
: 2 {(1,1),(2)}
: 3 {(1,1,1),(1,2),(3)}
: 4 {(1,1,1,1),(1,1,2),(1,3),(2,2),(4)}
: 感觉上应该用DP，可是又没啥思路。请各位大侠不吝赐教！谢谢！
|
|
