私はたまたまこのための Java コードを書きました。ご自由にどうぞ。ソリューションは広範囲にテストされていませんが、これまでのところうまく機能しているようです。
package expt.qp;
import java.util.HashMap;
import java.util.LinkedHashMap;
import java.util.Map;
public class LinearDiophantine {
private Map<Integer, Integer> sol = new LinkedHashMap<Integer, Integer>();
private Map<Integer, Integer> coeff = new HashMap<Integer, Integer>();
/**
* @param args
*/
public static void main(String[] args) {
// Fill up the data
// 3x + 4y + 5z + 3a = 25
LinearDiophantine ld = new LinearDiophantine();
ld.coeff.put(1, 1);ld.coeff.put(2, 2);ld.coeff.put(3, 3);ld.coeff.put(4, 4);
Map<Integer, Integer> coeffCopy = new HashMap<Integer, Integer>(ld.coeff);
int total=30;
// Real algo begins here
ld.findPossibleSolutions(total, coeffCopy);
}
private void findPossibleSolutions(int total, Map<Integer, Integer> coeff) {
int index=returnLargestIndex(coeff);
int range = (int) Math.floor(total/coeff.get(index));
if(range*coeff.get(index) == total) {
sol.put(index, range);
displaySolution();
//System.out.println();
range--;
}
if(coeff.size() == 1) {
return;
}
while(range>=0) {
int remTotal = total - range*coeff.get(index);
Map<Integer, Integer> coeffCopy = new HashMap<Integer, Integer>(coeff);
coeffCopy.remove(index);
sol.put(index, range);
findPossibleSolutions(remTotal, coeffCopy);
range--;
}
}
private void displaySolution() {
int total = 0;
for(int i : sol.keySet()) {
//System.out.print(coeff.get(i)+"("+sol.get(i)+"), ");
total = total + (coeff.get(i)*sol.get(i));
}
if(total != 30)
System.out.print(total+",");
}
/**
* @param coeff
*/
private int returnLargestIndex(Map<Integer, Integer> coeff) {
int largestKey = coeff.keySet().iterator().next();
for(int i : coeff.keySet()) {
if(coeff.get(i)>coeff.get(largestKey)) {
largestKey=i;
}
}
return largestKey;
}
}