logo
Redian新闻
>未名空间
>Parenting - 为人父母
>
替朋友问，要enfamil (1 year up) 奶粉么？限北京
avatar
替朋友问，要enfamil (1 year up) 奶粉么？限北京# Parenting - 为人父母
d*a
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);
}
avatar
j*1
2 楼
近期要回国，想兑换些人民币。
1. 问了boa，可以在建行atm机取现，不过要收取1％的foreign transaction fee。
2. 机场直接用美元兑换人民币。
大家有过在机场兑换的经验吗？不知道哪个划算一些？
谢谢！
avatar
l*d
3 楼
【 以下文字转载自 WaterWorld 讨论区 】
发信人: loveinmind (爱上你), 信区: WaterWorld
标 题: 替一个朋友问一下，有人要enfamil (1 year and up) 奶粉么？只限北京
发信站: BBS 未名空间站 (Thu Nov 17 11:33:38 2011, 美东)
他家有六七桶或者是八九桶enfamil 的enfagrow 的，1 year and up. 买给儿子吃的，
结果他不喜欢，不肯吃。如果您要的话，他们就省得带回来退掉了。
一桶差不多是二十多美金出头，就算20美金一桶好了。
请尽快联系我，他这个周末就要带回来了。 谢谢。
avatar
g*s
4 楼
dynamic programming, 假设你要面值S的所有组合，而你已知面值1 - (S-1)的所有组
合。
S的组合就是：
1的组合+（S-1)的组合任意配对，2的组合+（S-2）的组合任意配对。。。或者是（S-
任意单个硬币面值）的组合+该硬币的任意配对
删除重复
avatar
A*0
5 楼
boa

【在 j***1 的大作中提到】
: 近期要回国，想兑换些人民币。
: 1. 问了boa，可以在建行atm机取现，不过要收取1％的foreign transaction fee。
: 2. 机场直接用美元兑换人民币。
: 大家有过在机场兑换的经验吗？不知道哪个划算一些？
: 谢谢！
avatar
j*7
6 楼
Hope if does not offend you. But you can buy from Walgreen at $16.99 these
days. With coupons, it can cost around $10.
avatar
g*s
7 楼
不过感觉上可能还是backtracking快点吧。。就穷举一下所有硬币的可能组合
avatar
j*1
8 楼
知道了，多谢！

【在 A**********0 的大作中提到】
: boa
avatar
l*d
9 楼
他们是在北京要卖掉。
coupons 在哪里搞？
无所谓的，就是看看有没有在北京需要的，省得花邮费了。
没有人要就带回来退掉。

【在 j*******7 的大作中提到】
: Hope if does not offend you. But you can buy from Walgreen at $16.99 these
: days. With coupons, it can cost around $10.
avatar
d*a
10 楼
这个想法不错。不过我个人感觉如果照这个实现的话，代码应该比我贴的更长吧？

【在 g*******s 的大作中提到】
: dynamic programming, 假设你要面值S的所有组合，而你已知面值1 - (S-1)的所有组
: 合。
: S的组合就是：
: 1的组合+（S-1)的组合任意配对，2的组合+（S-2）的组合任意配对。。。或者是（S-
: 任意单个硬币面值）的组合+该硬币的任意配对
: 删除重复
avatar
A*0
11 楼
:)
the only thing is:
you may need to call boa to let them know when you will be using
the debit/atm card in china

【在 j***1 的大作中提到】
: 知道了，多谢！
avatar
B*n
13 楼
是否先用最大的无所谓吧,感觉用简单的循环就可以实现了.
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)
avatar
j*1
14 楼
嗯，已经打了。
没想到boa的汇率加上1％的foreign transaction fee后，竟然还比在这边机场直接用
美元兑换划算，看来机场兑换的汇率很低啊。。。

【在 A**********0 的大作中提到】
: :)
: the only thing is:
: you may need to call boa to let them know when you will be using
: the debit/atm card in china
avatar
l*a
15 楼
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)
avatar
h*s
16 楼
我见过mall里兑换的汇率，是5.3（1美元兑5.3人民币）.

【在 j***1 的大作中提到】
: 嗯，已经打了。
: 没想到boa的汇率加上1％的foreign transaction fee后，竟然还比在这边机场直接用
: 美元兑换划算，看来机场兑换的汇率很低啊。。。
avatar
F*0
17 楼
Looks like recursive is popular in interview
avatar
i*g
18 楼
这个是穿越到一年后吧。。

【在 h****s 的大作中提到】
: 我见过mall里兑换的汇率，是5.3（1美元兑5.3人民币）.
avatar
i*9
19 楼
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;istd::cout<}
std::cout<}
avatar
j*1
20 楼
哎，美元是越来越不值钱了：(

【在 h****s 的大作中提到】
: 我见过mall里兑换的汇率，是5.3（1美元兑5.3人民币）.
avatar
g*s
21 楼
我想了下，DP的过程应该可以更简化
假设你要面值S的所有组合，而你已知面值1 - (S-1)的所有组
合。
S的组合就是：
（S-任意单个硬币面值）的组合+该硬币的任意配对
删除重复
这样应该会比backtracking要快
avatar
r*y
22 楼

貌似我在机场见到的也是5.几
就是为了赚钱吧

【在 i****g 的大作中提到】
: 这个是穿越到一年后吧。。
avatar
h*k
23 楼
backtracking解法是硬币种类的exponential的复杂度，DP是关于S的线性的复杂度

【在 g*******s 的大作中提到】
: 我想了下，DP的过程应该可以更简化
: 假设你要面值S的所有组合，而你已知面值1 - (S-1)的所有组
: 合。
: S的组合就是：
: （S-任意单个硬币面值）的组合+该硬币的任意配对
: 删除重复
: 这样应该会比backtracking要快
avatar
c*7
24 楼
机场摆个摊场地费也很贵呀。
avatar
d*a
25 楼
Thanks for everyone's reply. I find backtracking is very great for solving
this problem. The code will become more clean when using it.
avatar
A*0
26 楼
99.999999% you will not get that 1% fee...
well if u did get it, plz come back and report details to us, then,
i'll send you 20 wb as a token...

【在 j***1 的大作中提到】
: 嗯，已经打了。
: 没想到boa的汇率加上1％的foreign transaction fee后，竟然还比在这边机场直接用
: 美元兑换划算，看来机场兑换的汇率很低啊。。。
avatar
g*s
27 楼
嗯，是的，如果有n个硬币种类,backtracking就相当于欠套了n个loop。n一大就没法做了

【在 h**k 的大作中提到】
: backtracking解法是硬币种类的exponential的复杂度，DP是关于S的线性的复杂度
avatar
j*1
28 楼
一定，我看到那个置顶帖了

【在 A**********0 的大作中提到】
: 99.999999% you will not get that 1% fee...
: well if u did get it, plz come back and report details to us, then,
: i'll send you 20 wb as a token...
avatar
c*n
29 楼
其实很简单的题往往很多人做不对，
你这个对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++){
avatar
q*8
30 楼
backtrack的复杂度是多少
avatar
h*k
31 楼
同学，业务还不熟练啊。复习一下如何输出n个元素的全排列或者所有组合的算法。和
这道题本质是一样的，需要用递归。

做了

【在 g*******s 的大作中提到】
: 嗯，是的，如果有n个硬币种类,backtracking就相当于欠套了n个loop。n一大就没法做了
avatar
i*9
32 楼
good point, any suggestion to remove the duplicates?

【在 c******n 的大作中提到】
: 其实很简单的题往往很多人做不对，
: 你这个对5 会出三种答案：2-3, 3-2, 5
: 重复的不应算。
: 我建议大家找工作， 一定要把题写成code , 加test case, 你会发现第一次都是错的
: 你要是一边写对，那就可以稳拿offer 了
avatar
s*l
33 楼
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?
avatar
i*9
34 楼
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.
avatar
j*t
35 楼
这个太对了!

【在 h**k 的大作中提到】
: backtracking解法是硬币种类的exponential的复杂度，DP是关于S的线性的复杂度
avatar
s*l
36 楼
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
avatar
l*a
37 楼
硬币种类越多，backtracking复杂度越高。
想请教，exponential是怎么算出来的。

【在 h**k 的大作中提到】
: backtracking解法是硬币种类的exponential的复杂度，DP是关于S的线性的复杂度
avatar
s*l
38 楼
k-ary tree.

【在 l*****a 的大作中提到】
: 硬币种类越多，backtracking复杂度越高。
: 想请教，exponential是怎么算出来的。
avatar
i*9
39 楼
how do we know if we don't compare current combination with old ones

【在 s*********l 的大作中提到】
: maintain the order during generating the combination
avatar
l*a
40 楼
那我能理解的exponential就只是upper bound，不像是tight bound。

【在 s*********l 的大作中提到】
: k-ary tree.
avatar
s*n
41 楼
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)
avatar
s*l
42 楼
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
avatar
s*l
43 楼
the minimum height is n/5 and maximum height is n/2

【在 l*****a 的大作中提到】
: 那我能理解的exponential就只是upper bound，不像是tight bound。
avatar
i*9
44 楼
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.
avatar
w*t
45 楼
哪位能给个完整的打印所有组合的 dp 的解法，search了网上的，好像很少有提到dp打
印所有组合
avatar
h*n
46 楼
应该用backtracking吧，它能够罗列所有满足要求的组合
DP一般用来解优化问题的

【在 w*********t 的大作中提到】
: 哪位能给个完整的打印所有组合的 dp 的解法，search了网上的，好像很少有提到dp打
: 印所有组合
avatar
w*t
47 楼
thanks,前面几位提到的dp O(nC)的算法不是打印所有组合的算法？

【在 h***n 的大作中提到】
: 应该用backtracking吧，它能够罗列所有满足要求的组合
: DP一般用来解优化问题的
avatar
w*t
48 楼
请问你连接里的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.
avatar
b*s
49 楼
无穷背包问题
avatar
b*n
50 楼
递归

【在 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)
avatar
y*m
51 楼
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)
相关阅读
问个X-RAY的问题小孩游泳硅胶帽哪里有卖？两岁娃半夜哭闹不止，已经持续大半个月了。。。Flu shotK-5选好书，读好书，让宝宝享受阅读、爱上阅读如何查住宅地址属于哪个校区？Six Flags五六岁小孩可玩的多吗？请问小孩办旅行证需要美国护照吗？晚上睡觉房间温度定成华氏几度最为 合适？？三岁半小朋友的能力有没有对粉笔画感兴趣的？枪击案，美国不让打孩子对还是错有谁有过zarbee natural cough (转载)家有咳嗽娃 (转载)有七八岁了还什么兴趣班都不上的孩子吗？版主你为什么删除我帖子该禁枪，但如果禁枪了，想犯罪的人还是会拿到枪激动一下，给被孩子一直纠缠的妈妈们一点曙光碰到特别bossy的小孩怎么办？
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章，不代表同意其说法或描述，仅为提供更多信息，也不构成任何建议。文章信息的合法性及真实性由其作者负责，与Redian.news及其运营公司无关。欢迎投稿，如发现稿件侵权，或作者不愿在本网发表文章，请版权拥有者通知本网处理。