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 楼
国内各大院线。保守估计，一周内不会下档。
l*c
5 楼
如果每种硬币无穷多: one dimension
如果每种硬币个数有限: multiple dimension
BOTH DP
【在 r****o 的大作中提到】
: 如果每种硬币无穷多，可以用DP，
: 但如果每种硬币个数有限，还能用DP吗？如果可以，应该怎么写这个DP算法？多谢先。
如果每种硬币个数有限: multiple dimension
BOTH DP
【在 r****o 的大作中提到】
: 如果每种硬币无穷多，可以用DP，
: 但如果每种硬币个数有限，还能用DP吗？如果可以，应该怎么写这个DP算法？多谢先。
r*o
6 楼
多谢，能不能具体点说怎么用多个dimension啊？
【在 l******c 的大作中提到】
: 如果每种硬币无穷多: one dimension
: 如果每种硬币个数有限: multiple dimension
: BOTH DP
【在 l******c 的大作中提到】
: 如果每种硬币无穷多: one dimension
: 如果每种硬币个数有限: multiple dimension
: BOTH DP
a*9
7 楼
是不是用D(i,b1,...bn)表示用至多bk个面值为ak的硬币表示i的最优解？
【在 r****o 的大作中提到】
: 多谢，能不能具体点说怎么用多个dimension啊？
【在 r****o 的大作中提到】
: 多谢，能不能具体点说怎么用多个dimension啊？
r*o
8 楼
可能吧，不过这样维数也太多了吧。
【在 a***9 的大作中提到】
: 是不是用D(i,b1,...bn)表示用至多bk个面值为ak的硬币表示i的最优解？
【在 a***9 的大作中提到】
: 是不是用D(i,b1,...bn)表示用至多bk个面值为ak的硬币表示i的最优解？
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
x*r
10 楼
不是了解你的意思，不过在我这个假设只有1和5的情况下，如果104全部选完了，那么
103也就剩1个
了，应该也是不能满足的
【在 r****o 的大作中提到】
: 有点道理，不过如果100和104都选完了硬币怎么办？
: 这样105就无解了。
: 但实际上存在可能使得105可以从103＋2得到。
:
: 排除这一个解
: 1了
103也就剩1个
了，应该也是不能满足的
【在 r****o 的大作中提到】
: 有点道理，不过如果100和104都选完了硬币怎么办？
: 这样105就无解了。
: 但实际上存在可能使得105可以从103＋2得到。
:
: 排除这一个解
: 1了
r*o
11 楼
等我想想，如果104是从99+5来的而不是从103+1来的，
那104全选完了，103未必只剩一个，是不是?
【在 x****r 的大作中提到】
: 不是了解你的意思，不过在我这个假设只有1和5的情况下，如果104全部选完了，那么
: 103也就剩1个
: 了，应该也是不能满足的
那104全选完了，103未必只剩一个，是不是?
【在 x****r 的大作中提到】
: 不是了解你的意思，不过在我这个假设只有1和5的情况下，如果104全部选完了，那么
: 103也就剩1个
: 了，应该也是不能满足的
x*r
12 楼
我这种特例下好像是可以的你看看对不对
如果104是99 + 5来的， 但是99是95 + 1 + 1 + 1 + 1
基本上104就是用了20个5和4个4
所以基本上是一个道理
但是不知道碰到更general的情况还行不行呀
【在 r****o 的大作中提到】
: 等我想想，如果104是从99+5来的而不是从103+1来的，
: 那104全选完了，103未必只剩一个，是不是?
如果104是99 + 5来的， 但是99是95 + 1 + 1 + 1 + 1
基本上104就是用了20个5和4个4
所以基本上是一个道理
但是不知道碰到更general的情况还行不行呀
【在 r****o 的大作中提到】
: 等我想想，如果104是从99+5来的而不是从103+1来的，
: 那104全选完了，103未必只剩一个，是不是?
B*t
13 楼
把背包问题搞懂了，这类问题都迎刃而解
【在 r****o 的大作中提到】
: 如果每种硬币无穷多，可以用DP，
: 但如果每种硬币个数有限，还能用DP吗？如果可以，应该怎么写这个DP算法？多谢先。
【在 r****o 的大作中提到】
: 如果每种硬币无穷多，可以用DP，
: 但如果每种硬币个数有限，还能用DP吗？如果可以，应该怎么写这个DP算法？多谢先。
r*o
14 楼
我没找到反例，呵呵。
可能你说的是对的。
【在 x****r 的大作中提到】
: 我这种特例下好像是可以的你看看对不对
: 如果104是99 + 5来的， 但是99是95 + 1 + 1 + 1 + 1
: 基本上104就是用了20个5和4个4
: 所以基本上是一个道理
: 但是不知道碰到更general的情况还行不行呀
可能你说的是对的。
【在 x****r 的大作中提到】
: 我这种特例下好像是可以的你看看对不对
: 如果104是99 + 5来的， 但是99是95 + 1 + 1 + 1 + 1
: 基本上104就是用了20个5和4个4
: 所以基本上是一个道理
: 但是不知道碰到更general的情况还行不行呀
x*r
15 楼
呵呵，我也不确定呀
请问你这个题是哪里看到的呢？
【在 r****o 的大作中提到】
: 我没找到反例，呵呵。
: 可能你说的是对的。
请问你这个题是哪里看到的呢？
【在 r****o 的大作中提到】
: 我没找到反例，呵呵。
: 可能你说的是对的。
r*o
16 楼
我也是前几天看到版上有人讨论的时候提到了一下这个问题，所以问问。呵呵。
【在 x****r 的大作中提到】
: 呵呵，我也不确定呀
: 请问你这个题是哪里看到的呢？
【在 x****r 的大作中提到】
: 呵呵，我也不确定呀
: 请问你这个题是哪里看到的呢？
相关阅读
Far from the madding crowd圣安德里亚斯观后感（削微剧透）目前为止今年最好看的电影是不是到处转载网文挖坑的id是不是站方雇佣的？ (转载)【预告】蚁人正式版预告关于纯种地球人的超级英雄影视剧的“小鲜肉”--《大都市小爱情》原著浅评电影【战狼】是在诋毁我人民军队我舍不得保罗沃克，但他还是走了《速7》为何火得离谱儿？为什么现在回看琼瑶剧会觉得有点矫情造作，回看金庸武侠剧会晓瑜：那些逝去的岁月--回顾几部苏联卫国战争电影 (转载)周末在家看了土星有人看了 San Andreas ？最新推出热门电影影！！！《搭上末班车》电影《战狼》一部意淫片传授孙悟空本领的师父菩提祖师的真实身份究竟是什么【海选】当当当！有声书《杜评金瓶梅》海选正式启动！ (转载)Code of a killer --观影及美剧纪录自己印象比较深的一段好莱坞打戏