由买买提看人间百态

boards

本页内容为未名空间相应帖子的节选和存档,一周内的贴子最多显示50字,超过一周显示500字 访问原贴
Science版 - 问题征解
相关主题
[转载] help, greedy algorithm田刚完证世界级数学难题庞加莱猜想[zz]
Re: Integer Optimization丘成桐的"封顶"骗局基本落幕.
Re: 难题征解,急!!!!mytbbs conjecture: 比较可怕, 美帝成功秘制seismic weapon
Re: 另外一道高中物理题-征解原创概率题
哥德巴赫猜想negative temperature?
Re: anyone knows the largest number checked forcosmo1
七道难题 解一题奖100万Re: 难题非高手莫入
Re: 请教:关于fractals and percolationRe: 请问uniformly bounded/convergent的意思
相关话题的讨论汇总
话题: greedy话题: algorithm话题: 134话题: 硬币话题: so
进入Science版参与讨论
1 (共1页)
z*y
发帖数: 1311
1
有一组面值为 25c 10c 5c 1c 的硬币,给定一个找钱数,
求证 greedy algorithm 能够找到最少的硬币数.
比如 134,使用 greedy algorithm 给出的结果是
5 个 25c 1 个 5c 和 4 个 1c 求证这是最优的解.
类似背包问题,要求装满一个包的物件个数最少.
a****y
发帖数: 1035
2
Need not to use greedy algorithm.
s=134;
n25= s/25;
s%=25;
n10= s/10;
s%=10;
n5= s/5;
s%=5
n1=s

【在 z*y 的大作中提到】
: 有一组面值为 25c 10c 5c 1c 的硬币,给定一个找钱数,
: 求证 greedy algorithm 能够找到最少的硬币数.
: 比如 134,使用 greedy algorithm 给出的结果是
: 5 个 25c 1 个 5c 和 4 个 1c 求证这是最优的解.
: 类似背包问题,要求装满一个包的物件个数最少.

z*y
发帖数: 1311
3

因为并不是任意的一组面值,贪婪算法都有最优解.比如
7c 6c 和 1c 贪婪算法就不一定会给出最少的找钱数.
这个问题明眼人一看就懂,还是请高手小露一把救救急.

【在 z*y 的大作中提到】
: 有一组面值为 25c 10c 5c 1c 的硬币,给定一个找钱数,
: 求证 greedy algorithm 能够找到最少的硬币数.
: 比如 134,使用 greedy algorithm 给出的结果是
: 5 个 25c 1 个 5c 和 4 个 1c 求证这是最优的解.
: 类似背包问题,要求装满一个包的物件个数最少.

a****y
发帖数: 1035
4
I don't know how to solve the general cases.
In the 7 6 1 case,
because 1*7+5*1 = 2*6 so greedy method won't good for 12
In the 25 10 5 1 case,
The number of 10 5 1 from greedy method can be at most 2 1 4;
They can't be combine with 25 to decrease cost. and so on... So greedy
method can get optimal cost.

【在 z*y 的大作中提到】
:
: 因为并不是任意的一组面值,贪婪算法都有最优解.比如
: 7c 6c 和 1c 贪婪算法就不一定会给出最少的找钱数.
: 这个问题明眼人一看就懂,还是请高手小露一把救救急.

w*******e
发帖数: 6802
5
Generally to show greedy algorithm works correctly need to use Matroid. In which
you need to construct the element set S, and the set family I. Well, I think
S is a certain amount of each kind of 硬币, I is the solution for 找钱数 from
1 to 134? Maybe won't work, try later :)

【在 z*y 的大作中提到】
:
: 因为并不是任意的一组面值,贪婪算法都有最优解.比如
: 7c 6c 和 1c 贪婪算法就不一定会给出最少的找钱数.
: 这个问题明眼人一看就懂,还是请高手小露一把救救急.

w**n
发帖数: 88
6
I happen to know the theorem for Greedy Algorithm ,but it looks ugly :-) :
1.If for some integer k and for any non-negative y , we have
G(k,y)=F(k,y)
*: G is the solution given by greedy algorithm ,and F is the real optimal
solution, here k means we only use the first k elements in the system, and
y is the given value.e.g. G(4,134)=F(4,134)=10
2.Assume v(k+1)=p*v(k)-d , 0<=d<=v(k) , p is a positive integer
*: v(k) is the value of the k-th element in the system and v(1)
【在 z*y 的大作中提到】
:
: 因为并不是任意的一组面值,贪婪算法都有最优解.比如
: 7c 6c 和 1c 贪婪算法就不一定会给出最少的找钱数.
: 这个问题明眼人一看就懂,还是请高手小露一把救救急.

w*******e
发帖数: 6802
7

Well, S is just the 4 kind of 硬币, so it is nonempty and finite.
I is not correct defined too.. I should be all of the sets has 最少的硬币数.
Try to prove the 3 attributes by yourself ba :)

【在 w*******e 的大作中提到】
: Generally to show greedy algorithm works correctly need to use Matroid. In which
: you need to construct the element set S, and the set family I. Well, I think
: S is a certain amount of each kind of 硬币, I is the solution for 找钱数 from
: 1 to 134? Maybe won't work, try later :)

d****i
发帖数: 11
8
so now it is clear that for v's = 1,5,10,25, the system works fine with
Greedy algorithm. For a set of different v's, G(k,y) may not be equal
to F(k,y) for all y's. I conjecture that even though G(k,y)>F(k,y) for
some y's, F(k,y) is bounded below by G(k,y)-C for all y's, where C is
a constant depending only on values of v's (not on y). If that's the
case, then the ratio G(k,y)/F(k,y) approaches unity when y approaches
infinity. In other words, when y is large, the result from Greedy
algorithm wi

【在 w**n 的大作中提到】
: I happen to know the theorem for Greedy Algorithm ,but it looks ugly :-) :
: 1.If for some integer k and for any non-negative y , we have
: G(k,y)=F(k,y)
: *: G is the solution given by greedy algorithm ,and F is the real optimal
: solution, here k means we only use the first k elements in the system, and
: y is the given value.e.g. G(4,134)=F(4,134)=10
: 2.Assume v(k+1)=p*v(k)-d , 0<=d<=v(k) , p is a positive integer
: *: v(k) is the value of the k-th element in the system and v(1)
1 (共1页)
进入Science版参与讨论
相关主题
Re: 请问uniformly bounded/convergent的意思哥德巴赫猜想
Re: Help: Line ArrangementRe: anyone knows the largest number checked for
[转载] how do you do integer division?七道难题 解一题奖100万
Higgs bosonRe: 请教:关于fractals and percolation
[转载] help, greedy algorithm田刚完证世界级数学难题庞加莱猜想[zz]
Re: Integer Optimization丘成桐的"封顶"骗局基本落幕.
Re: 难题征解,急!!!!mytbbs conjecture: 比较可怕, 美帝成功秘制seismic weapon
Re: 另外一道高中物理题-征解原创概率题
相关话题的讨论汇总
话题: greedy话题: algorithm话题: 134话题: 硬币话题: so