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)
|
|
