背包最优解（蛮力）

Question

用户将输入重量阈值、对象数量以及3个对象的重量和成本。输出应该是背包图，它应该显示最优解。

重量应该是最大的，成本应该是最小的。

示例输出：

w=60
n=3
w = 10
w2 = 35
w3 = 30
c=8
c1=4
c2=7

output:
A   10  8
B   35  4
C   30  7
AB  45  12
AC  40  15
BC  65  11
ABC 75  19

OPTIMAL SOLUTION: AB with total weight of 45 and total cost of 12.

我的问题是我的最优解是错误的。它输出 OPTIMAL SOLUTION: A with total weight of 40 and total cost of 15.

我该如何解决？

谢谢！

import java.util.*;
public class KnapsackBruteForce {
    static int numObject;
    static int weightThreshold = 0;
    static String variables[] = new String[100];
    static double numCombination;
    static KnapsackBruteForce knapsack = new KnapsackBruteForce();
    static Scanner input = new Scanner(System.in);
    public static void main(String args[]){
        System.out.print("Enter weight threshold: ");
        weightThreshold = input.nextInt();
        System.out.print("Enter number of objects: ");
        numObject = input.nextInt();

        int weightObject[] = new int[numObject+1];
        int costObject[] = new int[numObject+1];

        System.out.println("Enter variables: ");
        for(int i=0;i<numObject;i++){
            variables[i] = input.next();
        }
        for(int i=0;i<numObject;i++){
            System.out.print("Enter weight of object "+variables[i]+": ");
            weightObject[i] = input.nextInt();
        }
        for(int i=0;i<numObject;i++){
            System.out.print("Enter cost of object "+variables[i]+": ");
            costObject[i] = input.nextInt();
        }

        knapsack.possibleCombinations(variables, weightObject, costObject, weightThreshold, numObject);
    }

    public void possibleCombinations(String variables[], int weightObject[], int costObject[], int weightThreshold, int numObject){
        int weight = 0;
        int cost = 0;
        int optWeight = 0;
        int optCost = 0;
        String optVar = "";
        String newVar = "";

        for (int i = 1; i < (1 << numObject); i++) {
            String newVariable = Integer.toBinaryString(i);

            for (int j = newVariable.length() - 1, k = numObject - 1; j >= 0; j--, k--) {
                if (newVariable.charAt(j) == '1') {
                    newVar = variables[k];
                    weight += weightObject[k];
                    cost += costObject[k];
                    System.out.print(newVar);
                }
            }

            System.out.println("\t" + weight + "\t" + cost);

            if (weight <= weightThreshold) {
                if (optWeight == 0 && optCost == 0) {
                    optWeight = weight;
                    optCost = cost;
                } else if (optWeight <= weight) {
                    if (optCost <= cost) {
                        optVar = newVar;
                        optWeight = weight;
                        optCost = cost;
                    }
                }
            }

            weight = 0;
            cost = 0;
        }

        System.out.println("OPTIMAL SOLUTION: " + optVar + " with total weight of " + optWeight + " and total cost of " + optCost + ".");
    }
}

Answer 1

你的逻辑有优先级问题，如果你的解决方案中有两个最好的 45 12 和 50 13，你会选择哪个？

由于这种歧义，在下面的部分你不能选择：

            else if (optWeight <= weight) {
                if (optCost <= cost) {
                    optVar = newVar;
                    optWeight = weight;
                    optCost = cost;
                }
            }

此外，即使按照您的逻辑，您也应该选择较低的成本而不是较高的成本 optCost <= cost。

如果你清除了这个歧义，你应该关注的部分就是我提到的部分。

也可以使用日志记录或至少打印一些信息到控制台以查看代码的行为。

背包最优解（蛮力）

Knapsack Optimal Solution(Brute Force)

java

knapsack-problem

brute-force