d******a
发帖数: 238 | 1 有2， 3， 5 面值的多个硬币，给定一个值，打印出所有的组合。
这道题出现过在facebook, microsoft的面试中，还是很经典的。我的思路就是先用面
值最大的，可以有0到m个，然后再依次用面值次小的，依此类推。下面这个程序就是这
个想法，但感觉并不是很简单。
不知道大家有什么好想法？
void make_change_help(int n, int *result, int index, int demon)
{
int next_demon = 0, i;
if(n < 2)
return;
if(n == 0)
{
for(i = 0; i < index; i++)
printf("%d ", result[i]);
printf("\n");
return;
}
if(demon == 5)
next_demon = 3;
else if(demon == 3)
next_demon = 2;
else if(demon == 2)
{
if( n % demon == 0)
{
for(i = 0; i < index; i++)
printf("%d ", result[i]);
for(i = 0; i < n / demon; i++)
printf("%d ", demon);
printf("\n");
return;
}
return;
}
for(i = 0; i * demon <= n; i++)
{
int j;
for(j = 0; j <= i - 1; j++)
result[index + j] = demon;
make_change_help(n - i * demon, result, index + i, next_demon);
}
}
int make_change_1(int n)
{
int *result = (int *)malloc(sizeof(int) * n);
make_change_help(n, result, 0, 5);
} | g*******s
发帖数: 490 | 2 dynamic programming, 假设你要面值S的所有组合，而你已知面值1 - (S-1)的所有组
合。
S的组合就是：
1的组合+（S-1)的组合任意配对，2的组合+（S-2）的组合任意配对。。。或者是（S-
任意单个硬币面值）的组合+该硬币的任意配对
删除重复 | g*******s
发帖数: 490 | 3 不过感觉上可能还是backtracking快点吧。。就穷举一下所有硬币的可能组合 | d******a
发帖数: 238 | 4 这个想法不错。不过我个人感觉如果照这个实现的话，代码应该比我贴的更长吧？
【在 g*******s 的大作中提到】
: dynamic programming, 假设你要面值S的所有组合，而你已知面值1 - (S-1)的所有组
: 合。
: S的组合就是：
: 1的组合+（S-1)的组合任意配对，2的组合+（S-2）的组合任意配对。。。或者是（S-
: 任意单个硬币面值）的组合+该硬币的任意配对
: 删除重复
| B********n
发帖数: 384 | 5 是否先用最大的无所谓吧,感觉用简单的循环就可以实现了.
void PrintCoins(int n)
{
int i, j, k, l;
for (i = 0; i <= n/5; i++)
for (j = 0; j <= (n-5*i)/3; j++)
{
k = (n-5*i-3*j)/2;
if (k*2 == n-5*i-3*j)
{
for (l = 0; l < i; l++)
cout << "5 ";
for (l = 0; l < j; l++)
cout << "3 ";
for (l = 0; l < k; l++)
cout << "2 ";
cout << endl;
}
}
}
【在 d******a 的大作中提到】
: 有2， 3， 5 面值的多个硬币，给定一个值，打印出所有的组合。
: 这道题出现过在facebook, microsoft的面试中，还是很经典的。我的思路就是先用面
: 值最大的，可以有0到m个，然后再依次用面值次小的，依此类推。下面这个程序就是这
: 个想法，但感觉并不是很简单。
: 不知道大家有什么好想法？
: void make_change_help(int n, int *result, int index, int demon)
: {
: int next_demon = 0, i;
:
: if(n < 2)
| l*****a
发帖数: 14598 | 6 sort the array at first.
void GetCombination(int a[],int size,int target,int
start,vector&vec)
{
if(target==0) { print; return;}
for(int i=start;i
{
if(a[i]>target) return;
vec.pusk_back(a[i]);
GetCombination(a,size,target-a[i],i,vec);
vec.pop_back();
}
}
【在 d******a 的大作中提到】
: 有2， 3， 5 面值的多个硬币，给定一个值，打印出所有的组合。
: 这道题出现过在facebook, microsoft的面试中，还是很经典的。我的思路就是先用面
: 值最大的，可以有0到m个，然后再依次用面值次小的，依此类推。下面这个程序就是这
: 个想法，但感觉并不是很简单。
: 不知道大家有什么好想法？
: void make_change_help(int n, int *result, int index, int demon)
: {
: int next_demon = 0, i;
:
: if(n < 2)
| F*******0
发帖数: 28 | 7 Looks like recursive is popular in interview | i**9
发帖数: 351 | 8 This is a classic backtracking algorithm question.
int coins[3]={2, 3, 5}
void printCombinations(int sum,int number){
static int combinations[MAX_SIZE];//MAX_SIZE=sum/2;
if(sum ==0){
printArray(combinations,number);
}
else{
if(sum >0){
for(int i=0;i<3;i++){
combinations[number]=coins[i];
printCombinations(sum-coins[i],number+1);
}
}
}
}
void printArray(int a[],int length){
for(int i=0;i
std::cout<
}
std::cout<
} | g*******s
发帖数: 490 | 9 我想了下，DP的过程应该可以更简化
假设你要面值S的所有组合，而你已知面值1 - (S-1)的所有组
合。
S的组合就是：
（S-任意单个硬币面值）的组合+该硬币的任意配对
删除重复
这样应该会比backtracking要快 | h**k
发帖数: 3368 | 10 backtracking解法是硬币种类的exponential的复杂度，DP是关于S的线性的复杂度
【在 g*******s 的大作中提到】
: 我想了下，DP的过程应该可以更简化
: 假设你要面值S的所有组合，而你已知面值1 - (S-1)的所有组
: 合。
: S的组合就是：
: （S-任意单个硬币面值）的组合+该硬币的任意配对
: 删除重复
: 这样应该会比backtracking要快
| | | d******a
发帖数: 238 | 11 Thanks for everyone's reply. I find backtracking is very great for solving
this problem. The code will become more clean when using it. | g*******s
发帖数: 490 | 12 嗯，是的，如果有n个硬币种类,backtracking就相当于欠套了n个loop。n一大就没法做了
【在 h**k 的大作中提到】
: backtracking解法是硬币种类的exponential的复杂度，DP是关于S的线性的复杂度
| c******n
发帖数: 4965 | 13 其实很简单的题往往很多人做不对，
你这个对5 会出三种答案：2-3, 3-2, 5
重复的不应算。
我建议大家找工作， 一定要把题写成code , 加test case, 你会发现第一次都是错的
你要是一边写对，那就可以稳拿offer 了
【在 i**9 的大作中提到】
: This is a classic backtracking algorithm question.
: int coins[3]={2, 3, 5}
: void printCombinations(int sum,int number){
: static int combinations[MAX_SIZE];//MAX_SIZE=sum/2;
: if(sum ==0){
: printArray(combinations,number);
: }
: else{
: if(sum >0){
: for(int i=0;i<3;i++){
| q******8
发帖数: 848 | | h**k
发帖数: 3368 | 15 同学，业务还不熟练啊。复习一下如何输出n个元素的全排列或者所有组合的算法。和
这道题本质是一样的，需要用递归。
做了
【在 g*******s 的大作中提到】
: 嗯，是的，如果有n个硬币种类,backtracking就相当于欠套了n个loop。n一大就没法做了
| i**9
发帖数: 351 | 16 good point, any suggestion to remove the duplicates?
【在 c******n 的大作中提到】
: 其实很简单的题往往很多人做不对，
: 你这个对5 会出三种答案：2-3, 3-2, 5
: 重复的不应算。
: 我建议大家找工作， 一定要把题写成code , 加test case, 你会发现第一次都是错的
: 你要是一边写对，那就可以稳拿offer 了
| s*********l
发帖数: 103 | 17 make sure each output combination is sorted;
augment the combination only if appending the new coin does not break the
order.
【在 i**9 的大作中提到】
: good point, any suggestion to remove the duplicates?
| i**9
发帖数: 351 | 18 could u elaborate a bit, after finishing a combination then sort this
combination or sort in the process of generating combination?
if after finishing a combination then sorting , a lot of work for
comparing new combinations with old ones.
the
【在 s*********l 的大作中提到】
: make sure each output combination is sorted;
: augment the combination only if appending the new coin does not break the
: order.
| j*t
发帖数: 184 | 19 这个太对了!
【在 h**k 的大作中提到】
: backtracking解法是硬币种类的exponential的复杂度，DP是关于S的线性的复杂度
| s*********l
发帖数: 103 | 20 maintain the order during generating the combination
【在 i**9 的大作中提到】
: could u elaborate a bit, after finishing a combination then sort this
: combination or sort in the process of generating combination?
: if after finishing a combination then sorting , a lot of work for
: comparing new combinations with old ones.
:
: the
| | | l*****a
发帖数: 559 | 21 硬币种类越多，backtracking复杂度越高。
想请教，exponential是怎么算出来的。
【在 h**k 的大作中提到】
: backtracking解法是硬币种类的exponential的复杂度，DP是关于S的线性的复杂度
| s*********l
发帖数: 103 | 22 k-ary tree.
【在 l*****a 的大作中提到】
: 硬币种类越多，backtracking复杂度越高。
: 想请教，exponential是怎么算出来的。
| i**9
发帖数: 351 | 23 how do we know if we don't compare current combination with old ones
【在 s*********l 的大作中提到】
: maintain the order during generating the combination
| l*****a
发帖数: 559 | 24 那我能理解的exponential就只是upper bound，不像是tight bound。
【在 s*********l 的大作中提到】
: k-ary tree.
| s*****n
发帖数: 994 | 25 no repeats solution:
bool findCoins(int remain, int numTwo, int numThree, int numFive, string & s
){
bool found = false;
string s2 = "", s3 = "", s5 = "";
if (remain == 0)
{
s = "\n";
return true;
}
else if (remain < 2)
return false;
if (remain >= 2 && numTwo >= 1){
bool b = findCoins (remain - 2, numTwo - 1, numThree, numFive, s2);
if (b){
found = true;
size_t endOfLine(0);
string olds = "\n";
string news = " 2\n";
while ((endOfLine = s2.find (olds, endOfLine)) != string::npos){
s2.replace (endOfLine,olds.size(), news);
endOfLine += news.size();
}
}
}
if (remain >= 3 && numThree >= 1){
bool b = findCoins (remain - 3, 0, numThree - 1, numFive, s3);
if (b){
found = true;
size_t endOfLine(0);
string olds = "\n";
string news = " 3\n";
while ((endOfLine = s3.find (olds, endOfLine)) != string::npos){
s3.replace (endOfLine,olds.size(), news);
endOfLine += news.size();
}
}
}
if (remain >= 5 and numFive >= 1){
bool b = findCoins (remain - 5, 0, 0, numFive - 1, s5);
if (b){
found = true;
size_t endOfLine(0);
string olds = "\n";
string news = " 5\n";
while ((endOfLine = s5.find (olds, endOfLine)) != string::npos){
s5.replace (endOfLine,olds.size(), news);
endOfLine += news.size();
}
}
}
s = s2 + s3 + s5;
return found;
}
int main(){
string s = "";
findCoins (20,10,10,10,s);
cout << s;
}
【在 d******a 的大作中提到】
: 有2， 3， 5 面值的多个硬币，给定一个值，打印出所有的组合。
: 这道题出现过在facebook, microsoft的面试中，还是很经典的。我的思路就是先用面
: 值最大的，可以有0到m个，然后再依次用面值次小的，依此类推。下面这个程序就是这
: 个想法，但感觉并不是很简单。
: 不知道大家有什么好想法？
: void make_change_help(int n, int *result, int index, int demon)
: {
: int next_demon = 0, i;
:
: if(n < 2)
| s*********l
发帖数: 103 | 26 You don't need to compare current combination with old ones.
You just make sure each combination is sorted, for example,
7 = 2 + 5 (ok)
= 4 + 3 = 2 + 2 + 3 (ok)
= 5 + 2 (not ok, 2>5)
= 2 + 3 + 2 (not ok, 2>3)
Please see my Python code at
http://fayaa.com/code/view/16593/
There are two versions, one is naive memory-less recursion, another is recursion with dynamic programming which is much faster.
A non-recursive solution would be even better.
【在 i**9 的大作中提到】
: how do we know if we don't compare current combination with old ones
| s*********l
发帖数: 103 | 27 the minimum height is n/5 and maximum height is n/2
【在 l*****a 的大作中提到】
: 那我能理解的exponential就只是upper bound，不像是tight bound。
| i**9
发帖数: 351 | 28 Thanks! i got it now...
【在 s*********l 的大作中提到】
: You don't need to compare current combination with old ones.
: You just make sure each combination is sorted, for example,
: 7 = 2 + 5 (ok)
: = 4 + 3 = 2 + 2 + 3 (ok)
: = 5 + 2 (not ok, 2>5)
: = 2 + 3 + 2 (not ok, 2>3)
: Please see my Python code at
: http://fayaa.com/code/view/16593/
: There are two versions, one is naive memory-less recursion, another is recursion with dynamic programming which is much faster.
: A non-recursive solution would be even better.
| w*********t
发帖数: 170 | 29 哪位能给个完整的打印所有组合的 dp 的解法，search了网上的，好像很少有提到dp打
印所有组合 | h***n
发帖数: 276 | 30 应该用backtracking吧，它能够罗列所有满足要求的组合
DP一般用来解优化问题的
【在 w*********t 的大作中提到】
: 哪位能给个完整的打印所有组合的 dp 的解法，search了网上的，好像很少有提到dp打
: 印所有组合
| | | w*********t
发帖数: 170 | 31 thanks,前面几位提到的dp O(nC)的算法不是打印所有组合的算法？
【在 h***n 的大作中提到】
: 应该用backtracking吧，它能够罗列所有满足要求的组合
: DP一般用来解优化问题的
| w*********t
发帖数: 170 | 32 请问你连接里的dp是打印所有组合的算法马？有c 语言版本的吗
recursion with dynamic programming which is much faster.
【在 s*********l 的大作中提到】
: You don't need to compare current combination with old ones.
: You just make sure each combination is sorted, for example,
: 7 = 2 + 5 (ok)
: = 4 + 3 = 2 + 2 + 3 (ok)
: = 5 + 2 (not ok, 2>5)
: = 2 + 3 + 2 (not ok, 2>3)
: Please see my Python code at
: http://fayaa.com/code/view/16593/
: There are two versions, one is naive memory-less recursion, another is recursion with dynamic programming which is much faster.
: A non-recursive solution would be even better.
| b*******s
发帖数: 5216 | | b******n
发帖数: 4509 | 34 递归
【在 d******a 的大作中提到】
: 有2， 3， 5 面值的多个硬币，给定一个值，打印出所有的组合。
: 这道题出现过在facebook, microsoft的面试中，还是很经典的。我的思路就是先用面
: 值最大的，可以有0到m个，然后再依次用面值次小的，依此类推。下面这个程序就是这
: 个想法，但感觉并不是很简单。
: 不知道大家有什么好想法？
: void make_change_help(int n, int *result, int index, int demon)
: {
: int next_demon = 0, i;
:
: if(n < 2)
| y***m
发帖数: 7027 | 35 how about this?
看成 x1*a1 + x2*a2 + x3*a3 ... Xn*An = k,遍历a和x
array a[]={0,2,3,5}; // maybe more elements e.g. {0,2,5,7,3,9}..
calc("", 37, 1);
function calc(preStr,k,j){
for(i=k/a[j];i>-1;i--){
currentStr = "";
if(i>0)
currentStr = i + "*" + a[j];
if( preStr != "" && currentStr != "" )
currentStr = preStr + ", " + currentStr;
elseif( currentStr == "" )
currentStr = preStr;
if( k % a[j] == 0 )
print( currentStr + "\n" );
else if( j < a.size() )
calc( currentStr, k-i * a[j] , j+1 );
}
【在 d******a 的大作中提到】
: 有2， 3， 5 面值的多个硬币，给定一个值，打印出所有的组合。
: 这道题出现过在facebook, microsoft的面试中，还是很经典的。我的思路就是先用面
: 值最大的，可以有0到m个，然后再依次用面值次小的，依此类推。下面这个程序就是这
: 个想法，但感觉并不是很简单。
: 不知道大家有什么好想法？
: void make_change_help(int n, int *result, int index, int demon)
: {
: int next_demon = 0, i;
:
: if(n < 2)
|
|
