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)
相关阅读
2016年美国大选，你的决定关乎你后代将来 (转载)这样的孩子算是非常delay么？父母不理解孩子，总是拿自己想法说孩子一篇唤醒华人的好文：说说奥巴马的“强插计划” (转载)问下有请保姆缴税经验的同学经济不宽裕的离婚家庭的孩子，是不是上便宜点的大学?如何为宝宝做早期抚触(转载)请问小孩多大打耳扣合适哪里能给保姆做乙肝2对半的体检？没有保险孩子的手机请问小孩在学校被狗咬了怎么办？幼儿园小男孩淘气顽皮怎么解？不好意思问一下，美国哪种卫生巾是棉质的隔壁总是家庭暴力会不会影响我的孩子数学家出的智力题 2[bssd] 跟大娃父母们请教一下AMC 8育儿分享，一起学习更多育儿经 (转载)乍寒乍暖之下怎样预防宝宝生病 (转载)如何进行孩子的智力开发 (转载)这些看似是帮助孩子学习的，其实是危害孩子健康的。(转载)
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章，不代表同意其说法或描述，仅为提供更多信息，也不构成任何建议。文章信息的合法性及真实性由其作者负责，与Redian.news及其运营公司无关。欢迎投稿，如发现稿件侵权，或作者不愿在本网发表文章，请版权拥有者通知本网处理。