java - 背包最优解(暴力)

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.

我的问题是我的最佳解决方案是错误的。它输出最佳解决方案:A，总重量为 40，总成本为 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 .

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

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