l*n
2 楼
多谢
x*r
3 楼
同问 + 请问这个问题出处?
我的想法是,对当前最优解,组合的种类是唯一的,那如果为每一个最优解加一个已选
了哪几个的信息,那么以后的DP过程中如果这类已经选完了,那么就在DP判断的时候排除这一个解
例如: 如果有1, 5两种面值
DP[105] = Min (DP[100] + 1, DP[104] + 1)
however如果DP[100].Used = 5 * 20 但面值5的只有20张,那么就只能选DP[104] + 1了
不知道这样可不可行,会不会丢掉解 :P
【在 r****o 的大作中提到】
: 如果每种硬币无穷多,可以用DP,
: 但如果每种硬币个数有限,还能用DP吗?如果可以,应该怎么写这个DP算法?多谢先。
我的想法是,对当前最优解,组合的种类是唯一的,那如果为每一个最优解加一个已选
了哪几个的信息,那么以后的DP过程中如果这类已经选完了,那么就在DP判断的时候排除这一个解
例如: 如果有1, 5两种面值
DP[105] = Min (DP[100] + 1, DP[104] + 1)
however如果DP[100].Used = 5 * 20 但面值5的只有20张,那么就只能选DP[104] + 1了
不知道这样可不可行,会不会丢掉解 :P
【在 r****o 的大作中提到】
: 如果每种硬币无穷多,可以用DP,
: 但如果每种硬币个数有限,还能用DP吗?如果可以,应该怎么写这个DP算法?多谢先。
c*i
4 楼
国内各大院线。保守估计,一周内不会下档。
r*o
9 楼
有点道理,不过如果100和104都选完了硬币怎么办?
这样105就无解了。
但实际上存在可能使得105可以从103+2得到。
排除这一个解
1了
【在 x****r 的大作中提到】
: 同问 + 请问这个问题出处?
: 我的想法是,对当前最优解,组合的种类是唯一的,那如果为每一个最优解加一个已选
: 了哪几个的信息,那么以后的DP过程中如果这类已经选完了,那么就在DP判断的时候排除这一个解
: 例如: 如果有1, 5两种面值
: DP[105] = Min (DP[100] + 1, DP[104] + 1)
: however如果DP[100].Used = 5 * 20 但面值5的只有20张,那么就只能选DP[104] + 1了
: 不知道这样可不可行,会不会丢掉解 :P
这样105就无解了。
但实际上存在可能使得105可以从103+2得到。
排除这一个解
1了
【在 x****r 的大作中提到】
: 同问 + 请问这个问题出处?
: 我的想法是,对当前最优解,组合的种类是唯一的,那如果为每一个最优解加一个已选
: 了哪几个的信息,那么以后的DP过程中如果这类已经选完了,那么就在DP判断的时候排除这一个解
: 例如: 如果有1, 5两种面值
: DP[105] = Min (DP[100] + 1, DP[104] + 1)
: however如果DP[100].Used = 5 * 20 但面值5的只有20张,那么就只能选DP[104] + 1了
: 不知道这样可不可行,会不会丢掉解 :P
相关阅读
求借一个amc stubs免fandango手续费、谢谢!也说说《妖猫传》假如明星们都秃顶了,那会是什麽样子的画面,哈哈unidentified_title广电总局的存在,造就了电影特效发展《芳华》折射出的晦暗人性《摔跤吧,爸爸》告诉你,孩子不能娇惯unidentified_titlespiderboy--home coming,一部政治正确把我噎着了的电影 (转载)《非凡任务》——俗套但惊心动魄Fracture 里面Anthony Hopkins演得好unidentified_title《雷神3》确实不算是什么经典但是它好笑啊好莱坞不再拍出经典电影,跟社会背景有关吗?《芳华》拍的太消极了王男感觉有点土了unidentified_title《边境杀手》绝对是一部不能被忽视的佳作说什么《逆权司机》被禁鸟 (转载)袁立,一个真演员的诞生