高校问答河南有啥好玩的地方:帮忙，一个算法！急急急~~~~~~~~
来源：百度文库 编辑：高校问答 时间：2024/05/05 09:16:59
已知数M整数，
给定整数a,b,...,p（给定的个数不定，其中没有两两相同的数，M肯定是由这些数的倍数之和组成，如M=a*X+b*Y+...+p*Z
求需要多少个a，多少个b，...，多少个p之和组成M
比如
M=460,现有两个数a＝100，b＝80
求得3个a，2个b之和组成
请给个解的思路，不胜感激!!
有源代码更好了
给定整数a,b,...,p（给定的个数不定，其中没有两两相同的数，M肯定是由这些数的倍数之和组成，如M=a*X+b*Y+...+p*Z
求需要多少个a，多少个b，...，多少个p之和组成M
比如
M=460,现有两个数a＝100，b＝80
求得3个a，2个b之和组成
请给个解的思路，不胜感激!!
有源代码更好了
回溯 ...
给定整数a,b,...,p 依次保存在一个数组中，
然后 M 数组arr中第一个元素分解，
如果不符合，则退一步，
并加上第二个元素进行分解 ...
如 M＝460， arr[0]=100, arr[1]=80
1) arr[0]*1 = 100 < M
2) arr[0]*2 = 200 < M
3) arr[0]*3 = 300 < M
4) arr[0]*4 = 400 < M
5) arr[0]*5 = 500 > M 后退一步，并开始第二个元素的循环 ...
6) arr[0]*4 + arr[1]*1 = 460 == M 结束
这是个背包问题，好像只能搜索。给我个数据范围，我给你看看。
可以给我发短消息。
PS：你也是搞信息竞赛的？