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 的大作中提到】
: 呵呵，我也不确定呀
: 请问你这个题是哪里看到的呢？
相关阅读
这个杀手不太冷～～Shutter Island都是让发paper害的这俩看着好gay好gay的。。。Sam Worthington有没有来？靠。。。大局已定。。。。up in the air怎么两个女配角？Die hard系列哪一集值得收藏老屈穿的是牛仔裤啊人体蜈蚣。。。Re: 任达华《灭门》里的枪决，有多少是真的？（含剧透） (转载)魔戒的蓝光出来了为啥很多人黑色领带？Mary and Max 真好看那个超肥女Gabourey SidibeUP如果只有前30分钟这个visual最 no brainer.What's Green Zone? @_@此片一出，所有片子顿时黯淡无光。zzRocco's speech with the Saints (转载)