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)
相关阅读
Share Amazon Prime Membership真可耻！oggy and the cockroaches关于【输在起跑线上】请推荐irvine ob[限自用]Share Amazon Prime, $19/each, till Oct.30th 2015Re: 美国校园屠杀开始 女教师抱头鼠窜 (转载)求教：我女儿这种情况怎么办？3 岁小孩喜欢自言自语参加邻居的万圣节party带什么礼物？倔强娃该怎么对付？老公让我来问问他这样做对不对抵制“爸爸去哪儿了”，让全国看看5岁女童“环卫工”中文作业太花时间了国内离婚后的孩子抚养权记小女的一个同学中国老师打手心有人又打了鸡血了从来不用FB，为了小孩却不得不开始学习问一个关于入学年龄的问题
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章，不代表同意其说法或描述，仅为提供更多信息，也不构成任何建议。文章信息的合法性及真实性由其作者负责，与Redian.news及其运营公司无关。欢迎投稿，如发现稿件侵权，或作者不愿在本网发表文章，请版权拥有者通知本网处理。