puzzleup 9.23

wiley

Coins

It is possible to reach every value from 1 to 50 (both inclusive) using at most two of the coins used in a country. What is the possible minimum value of the sum of all coins in this country?

If the same question was asked for values from 1 to 8, the answer would be 8 (1+3+4)

{1}, {1+1}, {3}, {4}, {1+4}, {3+3}, {3+4}, {4+4}

一个国家的硬币系统, 对于任意从1到50的价值, 都可以用至多两个硬币来表示(可重复使用同一个硬币值), 问所有不同价值的硬币的和的最小值是多少?
例子: 如果是从1到8, 和的最小值是8, 可以用如下三个硬币: 1, 3和4.

目前搜索的结果: 10个硬币没有解; 11个硬币, 最小值是141.  还可以更少吗?

nlrte13

不可以

nlrte13

直接逆推就能得到答案了

wiley

麻烦你写一下逆推的过程 多谢

mathe

sum=140: 1 2 3 4 5 6 7 8 9 10 11 12 25 37

mathe

2. #define MAXDEPTH 20
3. #define MAXSUM 145
5. struct VALUE{
6. long long mask;
7. long long vlist;
8. int sum;
9. };
11. VALUE v[MAXDEPTH];
13. void dump(int depth)
14. {
15. int i;
16. printf("sum=%d:",v[depth].sum);
17. for(i=1;i<=50;i++){
18. if(v[depth].vlist&(1LL<<i)){
19. printf(" %d",i);
20. }
21. }
22. printf("\n");
23. }
25. void try_insert(int value, int depth)
26. {
27. int i;
28. if(value+v[depth-1].sum>MAXSUM)return;
29. v[depth].mask=v[depth-1].mask|(1LL<<value);
30. v[depth].vlist=v[depth-1].vlist|(1LL<<value);
31. v[depth].sum=v[depth-1].sum+value;
32. for(i=1;i<=50;i++){
33. if(v[depth].vlist&(1LL<<i)){
34. int j=i+value;
35. if(j<=50){
36. v[depth].mask|=1LL<<j;
37. }
38. }
39. }
40. for(i=1;i<=50;i++){
41. if((v[depth].mask&(1LL<<i))==0)
42. break;
43. }
44. int min_next=i;
45. if(min_next>50){
46. dump(depth);
47. return;
48. }
49. for(i=min_next;i>=value+1;i--){
50. try_insert(i,depth+1);
51. }
52. }
54. int _tmain(int argc, _TCHAR* argv[])
55. {
56. int used=1;
57. int min_next=3;
58. int i;
59. v[0].mask=2LL|4LL;
60. v[0].sum=1;
61. v[0].vlist=2LL;
62. for(i=min_next;i>=used+1;i--){
63. try_insert(i,1);
64. }
65. return 0;
66. }

复制代码

nlrte13

错了，唉。。。。

sjymb

老兄现在排第几位呀？

geslon

俺是140.

wayne

6# mathe 代码很棒