我必须编写一个程序，其中用户输入的数组和程序值计算 14、16 和 18 的总和以及该特定总和的元素组合的数量，同时浪费最少。
喜欢{3,6,12,7,1,4}
这里
14's sum=0 with wastage:0 And combination:0
16's sum=1 with wastage:0 And combination:12,4
18's sum=1 with wastage:1 And combination:3,6,7,1
Total Wastage:1
其他可以
14's sum=0 with wastage:0 And combination:0
16's sum=1 with wastage:1 And combination:3,7,1,4
18's sum=1 with wastage:0 And combination:12,6
Total Wastage:1
我认为这是最好的。
并且可以是其他浪费更大的组合。
现在的问题是我必须计算输入数组的排列(通过递归)，然后应用顺序计算任何排列的逻辑......并从所有排列中选择总浪费最少的最佳排列。我的代码适用于值从 1 到 7。从 8,9 或更多开始，由于排列数及其对象的增加，计算时间增加了很大的差异。我希望代码适用于大约 50 个数字。
谁能提出更好的解决方案或更改？
我的代码:
处理一种排列的类。
public class ResultSet {
public int fourteen = 0, sixteen = 0, eighteen = 0;
int ElementSum = 0, TotalWastage = 0, LastActivated = 0;
int[] FourteenWastages, SixteenWastages, EighteenWastages, InputCombination;
String[] FourteenCombination;
String[] SixteenCombination;
String[] EighteenCombination;
public ResultSet(int[] in) {
InputCombination = in;
FourteenWastages = new int[InputCombination.length];
SixteenWastages = new int[InputCombination.length];
EighteenWastages = new int[InputCombination.length];
FourteenCombination = new String[InputCombination.length];
SixteenCombination = new String[InputCombination.length];
EighteenCombination = new String[InputCombination.length];
selector();
wastagecalculator();
}
public void details() {
System.out.println("Fourteen: " + fourteen);
for (int j = 0; j < fourteen; j++) {
System.out.println("With wastegs:" + FourteenWastages[j] + "\tAnd Combination=" + FourteenCombination[j]);
}
System.out.println("---------------------");
System.out.println("Sixteen: " + sixteen);
for (int j = 0; j < sixteen; j++) {
System.out.println("With wastegs:" + SixteenWastages[j] + "\tAnd Combination=" + SixteenCombination[j]);
}
System.out.println("---------------------");
System.out.println("Eighteen: " + eighteen);
for (int j = 0; j < eighteen; j++) {
System.out.println("With wastegs:" + EighteenWastages[j] + "\tAnd Combination=" + EighteenCombination[j]);
}
System.out.println("---------------------");
System.out.println("Total Wastage=" + TotalWastage);
System.out.println("********************************");
}
final void selector() {
for (int j = 0; j < InputCombination.length; j++) {
ElementSum += InputCombination[j];
if (FourteenCombination[j] == null) {
FourteenCombination[j] = "";
}
if (SixteenCombination[j] == null) {
SixteenCombination[j] = "";
}
if (EighteenCombination[j] == null) {
EighteenCombination[j] = "";
}
FourteenCombination[fourteen] += InputCombination[j];
SixteenCombination[sixteen] += InputCombination[j];
EighteenCombination[eighteen] += InputCombination[j];
if (ElementSum <= 14) {
if (LastActivated != 1) {
if (LastActivated == 2) {
if (ElementSum + (16 - SixteenWastages[sixteen - 1]) <= 16) {
SixteenWastages[sixteen - 1] = 16 - (16 - SixteenWastages[sixteen - 1] + ElementSum);
SixteenCombination[sixteen - 1] += ElementSum;
FourteenCombination[fourteen] = SixteenCombination[sixteen] = EighteenCombination[eighteen] = "";
ElementSum = 0;
LastActivated = 2;
} else if (ElementSum + (16 - SixteenWastages[sixteen - 1]) <= 18) {
sixteen--;
eighteen++;
EighteenWastages[eighteen - 1] = 18 - (16 - SixteenWastages[sixteen] + ElementSum);
EighteenCombination[eighteen - 1] = SixteenCombination[sixteen] + ElementSum;
FourteenCombination[fourteen] = SixteenCombination[sixteen] = SixteenCombination[sixteen + 1] = "";
SixteenWastages[sixteen] = ElementSum = 0;
LastActivated = 3;
} else {
fourteen++;
FourteenWastages[fourteen - 1] = 14 - ElementSum;
ElementSum = 0;
SixteenCombination[sixteen] = EighteenCombination[eighteen] = "";
LastActivated = 1;
}
} else if (LastActivated == 3 && (ElementSum + (18 - EighteenWastages[eighteen - 1]) <= 18)) {
EighteenWastages[eighteen - 1] = 18 - (18 - EighteenWastages[eighteen - 1] + ElementSum);
EighteenCombination[eighteen - 1] += ElementSum;
FourteenCombination[fourteen] = SixteenCombination[sixteen] = EighteenCombination[eighteen] = "";
ElementSum = 0;
LastActivated = 3;
} else {
fourteen++;
FourteenWastages[fourteen - 1] = 14 - ElementSum;
ElementSum = 0;
SixteenCombination[sixteen] = EighteenCombination[eighteen] = "";
LastActivated = 1;
}
} else if (LastActivated == 1) {
if ((14 - FourteenWastages[fourteen - 1] + ElementSum) <= 14) {
FourteenWastages[fourteen - 1] = 14 - ((14 - FourteenWastages[fourteen - 1] + ElementSum));
ElementSum = 0;
FourteenCombination[fourteen - 1] += FourteenCombination[fourteen];
SixteenCombination[sixteen] = EighteenCombination[eighteen] = FourteenCombination[fourteen] = "";
LastActivated = 1;
} else if ((14 - FourteenWastages[fourteen - 1] + ElementSum) <= 16) {
fourteen--;
sixteen++;
SixteenWastages[sixteen - 1] = 16 - (14 - FourteenWastages[fourteen] + ElementSum);
FourteenWastages[fourteen] = 0;
SixteenCombination[sixteen - 1] = FourteenCombination[fourteen] + ElementSum;
FourteenCombination[fourteen] = EighteenCombination[eighteen] = "";
LastActivated = 2;
ElementSum = 0;
} else if ((14 - FourteenWastages[fourteen - 1] + ElementSum) <= 18) {
fourteen--;
eighteen++;
EighteenWastages[eighteen - 1] = 18 - (14 - FourteenWastages[fourteen] + ElementSum);
FourteenWastages[fourteen] = 0;
EighteenCombination[eighteen - 1] = FourteenCombination[fourteen] + ElementSum;
FourteenCombination[fourteen] = SixteenCombination[sixteen] = "";
LastActivated = 3;
ElementSum = 0;
} else {
fourteen++;
FourteenWastages[fourteen - 1] = 14 - ElementSum;
SixteenCombination[sixteen] = EighteenCombination[eighteen] = "";
LastActivated = 1;
ElementSum = 0;
}
}
} else if (ElementSum > 14 && ElementSum <= 16) {
sixteen++;
SixteenWastages[sixteen - 1] = 16 - ElementSum;
ElementSum = 0;
FourteenCombination[sixteen] = EighteenCombination[eighteen] = "";
LastActivated = 2;
} else if (ElementSum > 16 && ElementSum <= 18) {
eighteen++;
EighteenWastages[eighteen - 1] = 18 - ElementSum;
ElementSum = 0;
FourteenCombination[fourteen] = SixteenCombination[sixteen] = "";
LastActivated = 3;
}
}
}
final void wastagecalculator() {
for (int i = 0; i < fourteen; i++) {
TotalWastage += FourteenWastages[i];
}
for (int i = 0; i < sixteen; i++) {
TotalWastage += SixteenWastages[i];
}
for (int i = 0; i < eighteen; i++) {
TotalWastage += EighteenWastages[i];
}
}
}
主类:
public class Alumcalc {
public static int[][] InputCombinationsArray;
public static int[] InputArray ={11, 2, 16, 3, 15, 10};
public static ResultSet[] CombinationsArray, SortedCombinationsArray;
public static int Factorial;
public static void main(String[] args) {
Factorial = factorial(InputArray.length);
InputCombinationsArray = new int[Factorial][InputArray.length];
CombinationsArray = new ResultSet[Factorial];
Permute(InputArray, 0);
for (int i = 0; i < Factorial; i++) {
CombinationsArray[i] = new ResultSet(InputCombinationsArray[i]);
}
SortedCombinationsArray = CombinationsArray;
sort(); //From Other Class
topfive(); //From Other Class
}
}
现在
Permute(InputArray, 0);
for (int i = 0; i < Factorial; i++) {
CombinationsArray[i] = new ResultSet(InputCombinationsArray[i]);
}
正在花费时间..并且对于 10 或 > 排列的递归失败。
最佳答案
您正在解决经典的背包问题，这是著名的 NP 问题之一。根据定义，NP 问题对于任何更大的 N 都是棘手的(50 在这里绝对有资格作为大)。
没有关于如何改进代码的简单建议:您将不得不研究启发式 算法的各种选项，这些选项不能保证找到真正的最优值。不同的算法有不同的优点和缺点，艺术是找到最符合您问题的具体细节的算法。
关于java - 需要特定总和的数组元素的最佳组合，且浪费最少，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/20870150/