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 的大作中提到】
: 呵呵，我也不确定呀
: 请问你这个题是哪里看到的呢？
相关阅读
bt还真是不安全啊恐龙当家Mission Impossible 的几个看点大家推荐个网站看片吧佩服英伦爱情故事中国啥时候能拍出《Interstellar》这样的电影原来skydance是这个来历为什么说刘晓庆的人生开挂了？孙俪算个毛线一线明星，有人找她演电影么侏罗纪的暗喻 (转载)<大话西游><国产凌凌漆>经典电影法语版分享看了终结者创世纪，好无聊啊现在的电影真是在挑战我们的底线影视界的悲哀：论陈道明的走红史上最强3D全息时装秀AMC在重放《FF7》，没看过的，想再看的可以去哦孙杨霸气回应外媒：故意仇视中国选手显得很肮脏大圣归来，美国 上映吗？刺客聂隐娘的TC版出来了号外，迪斯尼筹拍ts4，i2，c3