- 主题:求解凑钱的贪心算法
已知分别价值为a元b元c元d元e元的五种商品，现在手里边有现金n元，求怎么买这五种商品才能使得花出去的钱无限接近于n元，但是又不超过n元。
想在网页上面用js脚本实现，但是目前看了别人几种算法不知道怎么改。
请教。
--
FROM 117.129.64.*
我的思路是先假设都买成a，看看能剩多少钱嗯，然后用剩下的钱再去买嗯，bcde里面最便宜的一种，如果不够，那么剩下的钱就是真的是最后剩下的钱，否则再减去那个最便宜之后，还是剩下的钱
最后，把所有的商品都遍历一遍，在做之前，先把所有的商品价格abcde做一个排序
--
FROM 117.129.64.*
你这个不对吧
假如a = 800, b = 300，n = 900，那么买0个a、3个b是符合要求的。
--
修改:z16166 FROM 221.218.160.*
FROM 221.218.160.*
动态规划，复杂度O(n*商品个数)
【 在 imchenghaibo 的大作中提到: 】
: 已知分别价值为a元b元c元d元e元的五种商品，现在手里边有现金n元，求怎么买这五种商品才能使得花出去的钱无限接近于n元，但是又不超过n元。
: 想在网页上面用js脚本实现，但是目前看了别人几种算法不知道怎么改。
: 请教。
: ...................
--
FROM 158.140.1.*
贪心不是最优解啊
【 在 imchenghaibo (南城码农) 的大作中提到: 】
: 已知分别价值为a元b元c元d元e元的五种商品，现在手里边有现金n元，求怎么买这五种商品才能使得花出去的钱无限接近于n元，但是又不超过n元。
:
: 想在网页上面用js脚本实现，但是目前看了别人几种算法不知道怎么改。
: 请教。
--
FROM 114.246.97.*
这个叫背包问题，你去搜了学习一下
【 在 imchenghaibo 的大作中提到: 】
: 已知分别价值为a元b元c元d元e元的五种商品，现在手里边有现金n元，求怎么买这五种商品才能使得花出去的钱无限接近于n元， ...
--
FROM 222.129.134.*
有道理，我想的是先遍历一遍，到时候比较？
【 在 z16166 的大作中提到: 】
: 你这个不对吧
假如a = 800, b = 300，n = 900，那么买0个a、3个b是符合要求的。
...
--
FROM 223.104.42.*
嗯，感觉很复杂
【 在 TGIF 的大作中提到: 】
: 这个叫背包问题，你去搜了学习一下
【 在 imchenghaibo 的大作中提到: 】
: 已知分别价值为a元b元c元...
--
FROM 223.104.42.*
还在消化，太复杂
【 在 TGIF 的大作中提到: 】
: 这个叫背包问题，你去搜了学习一下
【 在 imchenghaibo 的大作中提到: 】
: 已知分别价值为a元b元c元...
--
FROM 223.104.42.*
去b站找视频看吧，中学生信息奥林匹克的必学内容
【 在 imchenghaibo 的大作中提到: 】
: 还在消化，太复杂
--
FROM 123.127.143.*