筹码的面值怎样设计最好

yyy6 发表于 2012-12-20 13:08
嗯，N^1/C不是整数的时候而且C>3的情况是比较麻烦，C=3的时候我推过是N/K^2+K，后面递推就可以。但是你假 ...

需要推导当N为多少时，C=3的时候，（1，C3，C3^2）优过（1，C3，X）的方案，这里X为任意其它不同于C3^2的值。

但是对一开始并没有想到N为多少时，C3^2是更优解（相对任何非C3^2的X）的人，就需要用试验方法去证实，然后在（1，C3，C3^2）中过滤出最佳解就好。不费脑力的笨办法。

比如当X=C3^2-1的时候，而N=C3^2，以及N=（C3^2+1）的时候，X=C3^2-1显然更优。

这个题从实验方法上，我感觉就是最优解的不断逼近。

总之，这题我是从无从下手处用试验方法步步逼近，能找到点边就满足了。

另外：

“你这个数据总结有问题，其实1-9的时候SUM(3)是最小的，10-16SUM(4)是最小的，17-25SUM(5)是最小的，这就是我说的根号N. N = K^2-2到K^2的时候会出现两种方案一样的情况，你归类到下一种去了。”

1-9的时候实际上1种筹码是最小的，不需要2种，即C=1。

我明白你的意识，你计算的结果在这个意义上是正确的，但并不是唯一解。

比如N=8，9的时候，C=1 或者 C=2，而C2=3或者4都是最佳解。图省事的话，你的解能满足要求，严格的话，在某个很小的区段可以有几个解同时存在。 N=48的时候也类似，是否也会出现C=2的最佳解和某个C=3的最佳解在某个N值重合正如C=1和C=2在N=8，9的重合。


那么当C=4,5，...的时候，这个区段是否会扩大等等，未可知，我用的是试验方法，所以我的角度是观察所有变化，你用的是理论推导，所以可以排除一些数据。

我觉得是采用方法不同观察的角度不同，我侧重在临界值的变化发现规律。

再次给老陈道个谦，把这帖子搞的不简洁。

继续我的思路：

从C=2的结果可以看出，当（1，C2）在N=C2^2-2 附近达到最小值，那么类似的，（1，C2，C2^2）也可能会是在N=C2^3附近（或者C^4）达到最佳解，取C2=3，看（1,3,9）（9可以调整为其它大于3的数值）在27附近的值是多少。

依次类推，C2=4，5，6，7，8，9,10的时候，找出规律。

最终找出 C=M时，筹码面值和N的关系，这个数值我回头在EXCEL里试验下。

我的整个思路是：

当N达到多少时，需要用到第3种筹码？
然后是当N到另外一个数值时，需要用到第4种筹码，依次类推，这样就把N的不同区段用到的不同筹码种类和面值的问题都解决了。

N=48时，C=3，面值（1,4,16）的乘积比 C=2时候的所有面值（1，X）的乘积都小。
N=80时，C=3，面值（1,5,25）的乘积比（1,4,16）更优。

YY的公式大致看了下，当N的数值比较小的时候，K和C都会有很细微的偏差，可能和推理时对N的处理方法有关。

如果能确定（1，k,k^2,....k^m）一定是最佳的筹码分配方案，依此方案做求和不会太难，感觉这个方案靠谱，以后找个时间看能否证明下。（这几天颈部附近脊椎不好，睡眠极差，暂不耗神了。）

我不知道这个方案也不确定是否最优，能采用的只能是试验方法，先找规律，我的方法一向比较笨。

我找到了一个方案：
用3种筹码：1$, 11$ 和 19$
表示1到100筹码的总和为530
再乘以3等于1590
这是我找到的最好的方案。

竹林居士 发表于 2012-12-20 20:29
我找到了一个方案：
用3种筹码：1$, 11$ 和 19$
表示1到100筹码的总和为530

在我的陈述里面有一个地方忽略了 我假设第三个筹码是第二个筹码平方地时候最优 这在N^（1／m）是整数的时候成立 m是筹码种类
但是不是整数的时候不对 准确的数学公式应该是 第k个筹码是ceiling(N^(（k-1）／m)), 所以在N=100， m=3的时候第一个筹码是1， 第二个筹码是5， 第三个是22。 这个和是534的样子  你的算出来是536好像

竹林居士 发表于 2012-12-20 20:29
我找到了一个方案：
用3种筹码：1$, 11$ 和 19$
表示1到100筹码的总和为530

又算了一遍 1 11 19应该是536， 你可以确认一下

yyy6 发表于 2012-12-20 21:45
在我的陈述里面有一个地方忽略了 我假设第三个筹码是第二个筹码平方地时候最优 这在N^（1／m）是整数的时 ...

刚被朋友的电话叫醒，看见你和竹林的解答。

（1,5,22）*3的结果是1578，

即（1,5,22）的乘积和是526. 咱们的答案都不一致啊，这个是可以有标准答案的。

（1,11,19）的结果与我的计算相差较远，回头我再校验下，直觉上类似（1，X,2X）的方案可能不是最佳。

无论如何，可能都能说明，当N的数值不足够大的时候，（1，K,K^2,...K^M）未必是最佳方案，在这个思路上设计的方案对于特定的N会有偏颇。

C=2的时候很容易校验遍历（1,1）-（1，K）即可， C=3的时候校验起来比较麻烦。

基于老陈的题目，现在可以有一个明确答案的子问题：当N=100的时候，最佳方案是什么？

dfu2012 发表于 2012-12-20 22:18
刚被朋友的电话叫醒，看见你和竹林的解答。

（1,5,22）*3的结果是1578，

你没算表示100需要的8个筹码吧？
1，5，22应该是最小，和534。 方案是我重新列的那个: ceiling(N^((k-1)/m)), where k=1,2,3...m. 1,5,22都是直接代人这个公式算出来的。这个公式当N^(1/m)是整数时与你写那个等价

yyy6 发表于 2012-12-20 22:27
你没算表示100需要的8个筹码吧？
1，5，22应该是最小，和534。 方案是我重新列的那个: ceiling(N^((k-1)/ ...

我的方法和你的完全不同。

我用的是EXCEL，借用EXCEL的公式和复制功能，把1-100的和严格加一遍，按道理是不会出错的。

（1,5,22）的结果是526.

（1,5,19）的结果是540

（1,11,19）的结果是690，

(1，4，19)的结果是537.

先这些吧。

(1,11,19) 方案筹码个数如下，SUM=530

1        1
2        2
3        3
4        4
5        5
6        6
7        7
8        8
9        9
10        10
11        1
12        2
13        3
14        4
15        5
16        6
17        7
18        8
19        1
20        2
21        3
22        2
23        3
24        4
25        5
26        6
27        7
28        8
29        9
30        2
31        3
32        4
33        3
34        4
35        5
36        6
37        7
38        2
39        3
40        4
41        3
42        4
43        5
44        4
45        5
46        6
47        7
48        8
49        3
50        4
51        5
52        4
53        5
54        6
55        5
56        6
57        3
58        4
59        5
60        4
61        5
62        6
63        5
64        6
65        7
66        6
67        7
68        4
69        5
70        6
71        5
72        6
73        7
74        6
75        7
76        4
77        5
78        6
79        5
80        6
81        7
82        6
83        7
84        8
85        7
86        8
87        5
88        6
89        7
90        6
91        7
92        8
93        7
94        8
95        5
96        6
97        7
98        6
99        7
100        8

dfu2012 发表于 2012-12-20 22:47
我的方法和你的完全不同。

我用的是EXCEL，借用EXCEL的公式和复制功能，把1-100的和严格加一遍，按道理 ...

你的加法有问题1 11 19错太多了。真要用程序实现可以写递归的函数然后穷举。