E***n
发帖数: 166 | 1 给定一个整数数组，从大到小已经排好序，比如
30， 23， 10， 5， 2， 1
再给定一个整数，比如80，用给定数组中的元素来凑成80， 比如 80 = 30 + 30 + 10
+ 10
使得使用的元素个数最少（这个题目很像”找钱“，用有限的纸币的面值才凑数）。
我没有好的idea，
恳请高手指教！
刚才忘了说，1是永远存在数列里面的 |
s*********t
发帖数: 1663 | 2 google 背包问题
10
【在 E***n 的大作中提到】
: 给定一个整数数组，从大到小已经排好序，比如
: 30， 23， 10， 5， 2， 1
: 再给定一个整数，比如80，用给定数组中的元素来凑成80， 比如 80 = 30 + 30 + 10
: + 10
: 使得使用的元素个数最少（这个题目很像”找钱“，用有限的纸币的面值才凑数）。
: 我没有好的idea，
: 恳请高手指教！
: 刚才忘了说，1是永远存在数列里面的
|
p*********w
发帖数: 23432 | 3 从大往小凑。
凑不成功之后，就回退一级
10
【在 E***n 的大作中提到】
: 给定一个整数数组，从大到小已经排好序，比如
: 30， 23， 10， 5， 2， 1
: 再给定一个整数，比如80，用给定数组中的元素来凑成80， 比如 80 = 30 + 30 + 10
: + 10
: 使得使用的元素个数最少（这个题目很像”找钱“，用有限的纸币的面值才凑数）。
: 我没有好的idea，
: 恳请高手指教！
: 刚才忘了说，1是永远存在数列里面的
|
B*****t
发帖数: 335 | 4 NPC, 没什么通用的好方法。
如果数的个数小于25，DFS效率好一些。
否则的话用 psudo-polynomial的背包问题的标准解法。
10
【在 E***n 的大作中提到】
: 给定一个整数数组，从大到小已经排好序，比如
: 30， 23， 10， 5， 2， 1
: 再给定一个整数，比如80，用给定数组中的元素来凑成80， 比如 80 = 30 + 30 + 10
: + 10
: 使得使用的元素个数最少（这个题目很像”找钱“，用有限的纸币的面值才凑数）。
: 我没有好的idea，
: 恳请高手指教！
: 刚才忘了说，1是永远存在数列里面的
|
E***n
发帖数: 166 | 5 谢谢
但是这样不一定能找到最少的.如果我给定数组
10， 7， 1
要求凑14，那么从大往小凑需要14 = 10 + 1 + 1 + 1 + 1,实际上14 = 7 + 7，只要2个
【在 p*********w 的大作中提到】
: 从大往小凑。
: 凑不成功之后，就回退一级
:
: 10
|
s*********t
发帖数: 1663 | 6 可以重复使用也没关系
总之思路就是贪心地试验
2个
【在 E***n 的大作中提到】
: 谢谢
: 但是这样不一定能找到最少的.如果我给定数组
: 10， 7， 1
: 要求凑14，那么从大往小凑需要14 = 10 + 1 + 1 + 1 + 1,实际上14 = 7 + 7，只要2个
|
b******g
发帖数: 1721 | 7 hehe, very nice. It is a NPC problem like subset sum problem.
【在 B*****t 的大作中提到】
: NPC, 没什么通用的好方法。
: 如果数的个数小于25，DFS效率好一些。
: 否则的话用 psudo-polynomial的背包问题的标准解法。
:
: 10
|
r****o
发帖数: 1950 | 8 能不能贴一下代码或pseudo code?
多谢。
【在 p*********w 的大作中提到】
: 从大往小凑。
: 凑不成功之后，就回退一级
:
: 10
|
y**i
发帖数: 1112 | 9 回溯法可以么
10
【在 E***n 的大作中提到】
: 给定一个整数数组，从大到小已经排好序，比如
: 30， 23， 10， 5， 2， 1
: 再给定一个整数，比如80，用给定数组中的元素来凑成80， 比如 80 = 30 + 30 + 10
: + 10
: 使得使用的元素个数最少（这个题目很像”找钱“，用有限的纸币的面值才凑数）。
: 我没有好的idea，
: 恳请高手指教！
: 刚才忘了说，1是永远存在数列里面的
|
E***n
发帖数: 166 | 10 不能这么做，我最后用了dynamic programming.
Grady algorithm可能无法得到正确的结果，除非穷举，但是这样太慢了
【在 s*********t 的大作中提到】
: 可以重复使用也没关系
: 总之思路就是贪心地试验
:
: 2个
|
r****o
发帖数: 1950 | 11 你说的Greedy algorithm是用DFS搜索吗？
【在 E***n 的大作中提到】
: 不能这么做，我最后用了dynamic programming.
: Grady algorithm可能无法得到正确的结果，除非穷举，但是这样太慢了
|
E***n
发帖数: 166 | 12 dynamic programming,
和费波纳契数列比较类似
Backtracking可能需要返回不止一次，所以太麻烦了
【在 y**i 的大作中提到】
: 回溯法可以么
:
: 10
|
n******r
发帖数: 1247 | 13 Nice exercise for practising Knapsack problem
Let all items having weight 1, i.e. w_i=1, p_i being item i's value, A(Y)
being the min weight that can be achieved with total money Y (achieveable
becasue 1 is always there)
Then
A(0) = 0
A(Y)=min{1+A(Y-p_i)|p_i≤Y}
Calculate A(1),A(2),..., till you get A(80)
What kind of position is this interview for?
10
【在 E***n 的大作中提到】
: 给定一个整数数组，从大到小已经排好序，比如
: 30， 23， 10， 5， 2， 1
: 再给定一个整数，比如80，用给定数组中的元素来凑成80， 比如 80 = 30 + 30 + 10
: + 10
: 使得使用的元素个数最少（这个题目很像”找钱“，用有限的纸币的面值才凑数）。
: 我没有好的idea，
: 恳请高手指教！
: 刚才忘了说，1是永远存在数列里面的
|
c******f
发帖数: 2144 | |
