r****o
发帖数: 1950 | 1 如果每种硬币无穷多，可以用DP，
但如果每种硬币个数有限，还能用DP吗？如果可以，应该怎么写这个DP算法？多谢先。 |
x****r
发帖数: 99 | 2 同问 + 请问这个问题出处？
我的想法是，对当前最优解，组合的种类是唯一的，那如果为每一个最优解加一个已选
了哪几个的信息，那么以后的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算法？多谢先。
|
l******c
发帖数: 2555 | 3 如果每种硬币无穷多: one dimension
如果每种硬币个数有限: multiple dimension
BOTH DP
【在 r****o 的大作中提到】
: 如果每种硬币无穷多，可以用DP，
: 但如果每种硬币个数有限，还能用DP吗？如果可以，应该怎么写这个DP算法？多谢先。
|
r****o
发帖数: 1950 | 4 多谢，能不能具体点说怎么用多个dimension啊？
【在 l******c 的大作中提到】
: 如果每种硬币无穷多: one dimension
: 如果每种硬币个数有限: multiple dimension
: BOTH DP
|
a***9
发帖数: 364 | 5 是不是用D(i,b1,...bn)表示用至多bk个面值为ak的硬币表示i的最优解？
【在 r****o 的大作中提到】
: 多谢，能不能具体点说怎么用多个dimension啊？
|
r****o
发帖数: 1950 | 6 可能吧，不过这样维数也太多了吧。
【在 a***9 的大作中提到】
: 是不是用D(i,b1,...bn)表示用至多bk个面值为ak的硬币表示i的最优解？
|
r****o
发帖数: 1950 | 7 有点道理，不过如果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
|
x****r
发帖数: 99 | 8 不是了解你的意思，不过在我这个假设只有1和5的情况下，如果104全部选完了，那么
103也就剩1个
了，应该也是不能满足的
【在 r****o 的大作中提到】
: 有点道理，不过如果100和104都选完了硬币怎么办？
: 这样105就无解了。
: 但实际上存在可能使得105可以从103＋2得到。
:
: 排除这一个解
: 1了
|
r****o
发帖数: 1950 | 9 等我想想，如果104是从99+5来的而不是从103+1来的，
那104全选完了，103未必只剩一个，是不是?
【在 x****r 的大作中提到】
: 不是了解你的意思，不过在我这个假设只有1和5的情况下，如果104全部选完了，那么
: 103也就剩1个
: 了，应该也是不能满足的
|
x****r
发帖数: 99 | 10 我这种特例下好像是可以的你看看对不对
如果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
发帖数: 335 | 11 把背包问题搞懂了，这类问题都迎刃而解
【在 r****o 的大作中提到】
: 如果每种硬币无穷多，可以用DP，
: 但如果每种硬币个数有限，还能用DP吗？如果可以，应该怎么写这个DP算法？多谢先。
|
r****o
发帖数: 1950 | 12 我没找到反例，呵呵。
可能你说的是对的。
【在 x****r 的大作中提到】
: 我这种特例下好像是可以的你看看对不对
: 如果104是99 + 5来的， 但是99是95 + 1 + 1 + 1 + 1
: 基本上104就是用了20个5和4个4
: 所以基本上是一个道理
: 但是不知道碰到更general的情况还行不行呀
|
x****r
发帖数: 99 | 13 呵呵，我也不确定呀
请问你这个题是哪里看到的呢？
【在 r****o 的大作中提到】
: 我没找到反例，呵呵。
: 可能你说的是对的。
|
r****o
发帖数: 1950 | 14 我也是前几天看到版上有人讨论的时候提到了一下这个问题，所以问问。呵呵。
【在 x****r 的大作中提到】
: 呵呵，我也不确定呀
: 请问你这个题是哪里看到的呢？
|
