|
|---|
|
|
|
|
|
|
i*********7
发帖数: 348 | 1 You are given an integer N and an integer M. You are supposed to write a
method void findBestCoinsThatMinimizeAverage(int N, int M) that prints the
best collection of N coins that minimize the average number of minimum coins
needed to generate values from 1 to M. So, if M = 100, and N = 4, then if
we use the set {1, 5, 10, 25} to generate each value from 1 to 100, so that
for each value the number of coins are minimized, i.e. 1 = 1 (1 coin), 2 = 1
+ 1 (2 coins),..., 6 = 1 + 5 (2 coins), ..., 24 = 5 + 5 + 5 + 5 + 1 + 1 + 1
+ 1 (8 coins), and we take the average of these coins, we would see that
the average comes out to ~5.7. But if we instead use {1, 5, 18, 25}, the
average would come out to be 3.7. We are to find that set of N coins, and
print them, that produce the minimum average. | z****x
发帖数: 25 | 2 24 为什么不拆成 10+10+1+1+1+1 呢？ | p*****2
发帖数: 21240 | | h********6
发帖数: 285 | 4 貌似N是fixed number，用了10的硬币后之前的某一种就不能用了
【在 z****x 的大作中提到】
: 24 为什么不拆成 10+10+1+1+1+1 呢？
| l***i
发帖数: 1309 | 5 As pointed by an earlier reply, 24 = 10 + 10 + 1 + 1, so the example is
incorrect. That aside, here is a DP solution which might not be the best
possible.
Let dp[K][N][last] be a bool array such that
dp[i][j][k] is true if there exists a set of j coins with largest coin being
k, and was able to generate 1 to M with a sum of i coins.
To minimize average is the same as minimize the sum over 1 to M.
Then we are looking for the smallest K that dp[K][N][last] is true. K is at
most (1+...+M)=1/2 M^2, last is at most M. So the algorithm runs in time O(M
^3 * N), for M=100 and N<=10, this is fast enough.
coins
that
1
1
【在 i*********7 的大作中提到】
: You are given an integer N and an integer M. You are supposed to write a
: method void findBestCoinsThatMinimizeAverage(int N, int M) that prints the
: best collection of N coins that minimize the average number of minimum coins
: needed to generate values from 1 to M. So, if M = 100, and N = 4, then if
: we use the set {1, 5, 10, 25} to generate each value from 1 to 100, so that
: for each value the number of coins are minimized, i.e. 1 = 1 (1 coin), 2 = 1
: + 1 (2 coins),..., 6 = 1 + 5 (2 coins), ..., 24 = 5 + 5 + 5 + 5 + 1 + 1 + 1
: + 1 (8 coins), and we take the average of these coins, we would see that
: the average comes out to ~5.7. But if we instead use {1, 5, 18, 25}, the
: average would come out to be 3.7. We are to find that set of N coins, and
| i*********7
发帖数: 348 | 6 我也在想brute force。
我上glass door的时候发现的这道题。
有回复指出。。这题是来自一个滑铁卢大学的教授的论文的副产品。。
我看了一下那篇论文，当时那个教授为了论证最好要有一种18分的硬币，提出了这道题
目去论证。
发现最优解里面有18分。。
当时那个教授就是用Brute force做的。。
真心要命。
【在 p*****2 的大作中提到】
: bruteforce搞搞吧。
| i*********7
发帖数: 348 | 7 话说facebook对 bug free的要求是不是很高？
=.=
。。。要命了啊。。。orz.....
【在 p*****2 的大作中提到】
: bruteforce搞搞吧。
| p********s
发帖数: 37 | 8 赞思路，不过能贴下状态转移方程不？
being
at
(M
【在 l***i 的大作中提到】
: As pointed by an earlier reply, 24 = 10 + 10 + 1 + 1, so the example is
: incorrect. That aside, here is a DP solution which might not be the best
: possible.
: Let dp[K][N][last] be a bool array such that
: dp[i][j][k] is true if there exists a set of j coins with largest coin being
: k, and was able to generate 1 to M with a sum of i coins.
: To minimize average is the same as minimize the sum over 1 to M.
: Then we are looking for the smallest K that dp[K][N][last] is true. K is at
: most (1+...+M)=1/2 M^2, last is at most M. So the algorithm runs in time O(M
: ^3 * N), for M=100 and N<=10, this is fast enough.
| l***i
发帖数: 1309 | 9 sorry, my dp approach is incorrect. It seems dp may not even work, as the
problem does not satisfy principle of optimality, optimal solution to a
larger instance may not contain optimal solution to a smaller instance. | p********s
发帖数: 37 | 10 嗯俺也这么觉得的，只能想到枚举所有的硬币组合然后dp最少需要多少枚。
也考虑过费用流，不过建不出模型
【在 l***i 的大作中提到】
: sorry, my dp approach is incorrect. It seems dp may not even work, as the
: problem does not satisfy principle of optimality, optimal solution to a
: larger instance may not contain optimal solution to a smaller instance.
| t****a
发帖数: 1212 | 11 1、最简单办法是穷举, choose(m, n)，但计算量太大
2、改进的办法是搜索，也就是给出coin集合的情况下，搜索另一个更好的coin集合。
可以一步步去搜索，前提是本题的解要满足局部最优解=全局最优解的条件（我还不会
证明这一点）。这个方法的计算复杂度已经大大低于1
3、更好的的办法是迭代法，通过n-1个coin的解来算n个coin的解
4、可能存在某个解析的方法（比如写出方程式，求偏导数=0，解方程组）一步计算出
所有的coin取值。方程组可以写出，但由于存在coin的取值全部为正整数的约束条件，
偏倒数=0无法得到正整数解。
呼唤高人来给出3、4的解法。
----------------------------------------
推不出策略3的解，所以我去尝试策略2：
首先要猜一个不错的初始取值，
然后在它的基础上进行搜索。
我猜的解是:
C_n = (M^(n-1))^(1/n)
C_{n-1} = (M^(n-2))^(1/(n-1))
...
C_1 = (C_2^0)^1 = 1
clojure code如下 (不包含搜索的部分)
(use 'clojure.contrib.math)
(defn setvalue [m n]
(if (= n 1)
[1]
(let [cnguess (round (expt (expt m (dec n)) (/ 1 n)))
lastc (max cnguess n)
rst ((dec setvalue) lastc (dec n))]
(conj rst lastc))))
(defn countcoin [m values]
(if (zero? m)
0
(let [lst (last values)
btlst (pop values)
d (quot m lst)
r (rem m lst)
subcount (countcoin r btlst)]
(+ subcount d))))
(defn cumcountcoin [m values]
(let [i (map inc (range m))
cci (map #(countcoin % values) i)]
(apply + cci)))
(defn mincoin [m n]
(let [values (setvalue m n)
total (cumcountcoin m values)
avg (/ total m)]
{:avg avg :values values}))
(mincoin 100 4)； {:avg 417/100, :values [1 3 10 32]}
这个解比原题中给出的例子解好，原题中[1 5 18 25]的结果是462/100. |
|
|
|
|
|
|
|
