求纸币数目最少有关问题。

求纸币数目最少问题。。
一种新的货币系统：由n种不同面值的纸币组成，各种面值的纸币可以多张叠加、相互搭配使用

测试1--K元面值，求要组成1--K元，分别要使用至少多少张纸币。。

例如：n=3 分别为1 2 5元

k=10

则分别求
1=1 1张
2=2 1张
3=1+2 2张
4=2+2 ..
5=2+2+1 3张
6=2+2+2 ..
...

注意，贪心的结果可能是错的。。



[解决办法]
跟这个问题差不多，LZ看看吧。

http://topic.csdn.net/u/20100302/16/01c2a095-c7af-43a3-877b-cd75267d7baa.html
[解决办法]
BFS或DP都可以解

1 2 5 10 20
f(100) = min(f(99),f(98),f(95),f(90),f(80)) + 1
[解决办法]
基本上就是这样，上面给的是状态转移方程，其实基本上用贪心是可以的，bfs和dp只要计算一个很小的范围就可以了，剩下的靠贪心。

探讨

f(100) = min(f(99),f(98),f(95),f(90),f(80)) + 1

f(value)表示value价值时最少张数,每次可以选那么几种，选一种需要最少的+1就是现在的张数，DP记录一下。是这样么。

[解决办法]
对于一个硬币系统，贪心是否一直是最优解，这个存在强多项式的。没记错的话O(n^3)

当然和lz的问题是不一样的。
[解决办法]
从前往后走
1 2 5
是吧，
先把 1 2 5 给填了。
再填 3，4，6，7，10
再填 8、9 

这样就好了。
[解决办法]
嗯，就是BFS

探讨

从前往后走
1 2 5
是吧，
先把 1 2 5 给填了。
再填 3，4，6，7，10
再填 8、9

这样就好了。

查看更多 下一篇