wiley 发表于 2009-9-25 07:22:02

puzzleup 9.23

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 发表于 2009-9-25 08:57:01

不可以

nlrte13 发表于 2009-9-25 08:59:14

直接逆推就能得到答案了

wiley 发表于 2009-9-26 00:41:18

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

mathe 发表于 2009-9-26 14:56:31

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

mathe 发表于 2009-9-26 14:57:38


#define MAXDEPTH 20
#define MAXSUM   145

struct VALUE{
    long long mask;
    long long vlist;
    int sum;
};

VALUE v;

void dump(int depth)
{
    int i;
    printf("sum=%d:",v.sum);
    for(i=1;i<=50;i++){
      if(v.vlist&(1LL<<i)){
            printf(" %d",i);
      }
    }
    printf("\n");
}

void try_insert(int value, int depth)
{
    int i;
    if(value+v.sum>MAXSUM)return;
    v.mask=v.mask|(1LL<<value);
    v.vlist=v.vlist|(1LL<<value);
    v.sum=v.sum+value;
    for(i=1;i<=50;i++){
      if(v.vlist&(1LL<<i)){
            int j=i+value;
            if(j<=50){
                v.mask|=1LL<<j;
            }
      }
    }
    for(i=1;i<=50;i++){
      if((v.mask&(1LL<<i))==0)
            break;
    }
    int min_next=i;
    if(min_next>50){
      dump(depth);
      return;
    }
    for(i=min_next;i>=value+1;i--){
      try_insert(i,depth+1);
    }
}

int _tmain(int argc, _TCHAR* argv[])
{
    int used=1;
    int min_next=3;
    int i;
    v.mask=2LL|4LL;
    v.sum=1;
    v.vlist=2LL;
    for(i=min_next;i>=used+1;i--){
      try_insert(i,1);
    }
        return 0;
}

nlrte13 发表于 2009-9-27 14:14:23

错了，唉。。。。

sjymb 发表于 2009-9-27 23:19:58

老兄现在排第几位呀？

geslon 发表于 2009-10-1 22:30:57

俺是140.

wayne 发表于 2012-3-9 11:09:12

6# mathe
代码很棒
页: [1]
查看完整版本: puzzleup 9.23