求解n元一次不定方程解法

Question

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);
分不多了 ，请大虾出手相助！

Answer 1

20X+30Y+50Z+100K+.........=13000
求X+Y+Z+K+........的和最小的解的话...
因为是齐次的 
所以全部选出系数最大的那个来直到超过13000 然后剩下的再用剩下的最大的拿这个当例子
20X+30Y+50Z+120K=13000
K取到10
20X+30Y+50Z=1000
然后Z取20 完成所以思路就是把系数最大的数取尽可能大的值 然后递归就行了
程序知道思路后比较简单就不写了

Answer 2

不就是白鸡问题吗？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
因为108*120=12960
然后Y,Z都取0
X取2

Answer 3

请看题目呀 20X+30Y+50Z+100K+.........=13000
未知数的个数是变化的，并且要求出所有解

Answer 4

简化一下题目，求n元一次不定方程的正整数解
a1x1+a2x2+.......+anxn=sum
其中a1,a2....an,sum为已知数且为正整数
求x1,x2....xn未知数的0或正整数解

Answer 5

这个算法可以了
public class STest {
    static int[] values={50,30,20};
    static boolean flag=false;
    public static void main(String[] args) {
        split(300,0,"");
    }
    
    public static void split(int n,int base,String result){
        if(n<0) return;
        if(n==0){
            System.out.println(result);
            flag=true;
            return;
        }
        for(int i=base;i<values.length;i++){
            split(n-values[i],i,result+values[i]+"|");
            if(flag){
             break;
            }
        }
    }
}