日期:2014-05-20  浏览次数:20521 次

求解n元一次不定方程解法
private static HashMap<Integer, Long> map = new HashMap<Integer, Long>();
map.put(20, 10000L);
map.put(30,10000L);
map.put(50,10000L);
map.put(100,100000L);
map.put.......这里面的值可以自由添加
invoiceSelectMethod(map, 13000L);

key值可以看成常数,10000L可以看成系数,13000L看成和
所以可以写成20X+30Y+50Z+100K+.........=13000
X,Y,Z,K........的取值范围 0<=X<=10000,0<=Y<=10000,0<=Z<=10000
不需要算出每种满足要求的X,Y,Z......的组合,只需要求出X+Y+Z+K+......最小的组合即系数之和最小的组合。
请写出这个方法invoiceSelectMethod(map, 13000L);
分不多了 ,请大虾出手相助!


------解决方案--------------------
20X+30Y+50Z+100K+.........=13000
求X+Y+Z+K+........的和最小的解的话...
因为是齐次的 
所以全部选出系数最大的那个来直到超过13000 然后剩下的再用剩下的最大的

拿这个当例子
20X+30Y+50Z+120K=13000
K取到10
20X+30Y+50Z=1000
然后Z取20 完成

所以思路就是把系数最大的数取尽可能大的值 然后递归就行了
程序知道思路后比较简单就不写了
------解决方案--------------------
tree
------解决方案--------------------
探讨
自己顶下 如果要求出所有的解 如何做呢

------解决方案--------------------
探讨

引用:
自己顶下 如果要求出所有的解 如何做呢

不就是白鸡问题吗?

20X+30Y+50Z+120K=13000
4个for循环解决
x范围[0,13000/20]
y范围[0,13000/30]
其他类似

至于最小系数和可以参考2L
不过纠正一下2L
K取10的时候120K=1200不是12000!

所以K应该取13000/120=108……

------解决方案--------------------
探讨

引用:
引用:

引用:
自己顶下 如果要求出所有的解 如何做呢

不就是白鸡问题吗?

20X+30Y+50Z+120K=13000
4个for循环解决
x范围[0,13000/20]
y范围[0,13000/30]
其他类似

至于最小系数和可以参考2L
不过纠正一下2L
K取10的时候120K=1200不是1……

------解决方案--------------------
2楼正解啊!