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

1. 
   
2. #define MAXDEPTH 20
   
3. #define MAXSUM   145
   
4. 
   
5. struct VALUE{
   
6.     long long mask;
   
7.     long long vlist;
   
8.     int sum;
   
9. };
   
10. 
    
11. VALUE v[MAXDEPTH];
    
12. 
    
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. }
    
24. 
    
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. }
    
53. 
    
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
代码很棒