java - 背包问题暴力算法时间复杂度巨大

Question

我正在为我的学校项目使用暴力方法，问题是使用我当前的代码需要 15 个小时来计算，而我知道最多只需要几分钟。而且似乎没有选择最好的可能性，不知道为什么。它可以编译并且一切正常，但效率太低了。 我有一个包含数据的文件，其中第一行有容量，下一行有值(value)和重量。 我可以做些什么来改进代码？

public class Main {

    static ArrayList<String> weights = new ArrayList<>();
    static ArrayList<String> values = new ArrayList<>();
    static int n = 20;
    private static int maxValue = 0;

    public static void readFile(String dataFile) throws IOException {
        FileReader read = new FileReader(dataFile);
        BufferedReader buff = new BufferedReader(read);
        String line;
        while ((line = buff.readLine()) != null) {
            String[] item = line.split(" ");
            if (item.length == 1)
                capacity = Integer.parseInt(item[0]);
            else {
                values.add(item[0]);
                weights.add(item[1]);

            }
        }
    }

    public static String toBinary(int a) {
        String result = "";
        while (a > 0) {
            result = a % 2 + result;
            a = a / 2;

        }
        while (result.length() < n) {
            result = "0" + result;
        }
        return result;

    }

    public static boolean isMaxValue(int val) {
        if (val > maxValue)
            return true;
        return false;
    }

    public static boolean isInCapacity(int weight) {
        if (weight <= capacity)
            return true;
        return false;
    }

    public static void main(String[] args) {

        long start = System.currentTimeMillis();

        try {
            readFile(dataFile);
        } catch (IOException e) {
            e.printStackTrace();
        }

        int sumValue = 0;
        int sumWeight = 0;
        String bestComb = "";
        String finalResult = "";
        int combnum = (int) Math.pow(2, n);

        for (int i = 1; i < combnum; i++) { /

            //System.out.println(toBinary(i));  // 277s with, without 187s for n=20

            for (int j = 0; j < toBinary(i).length(); j++) {

                int arrElem = Character.getNumericValue(toBinary(i).charAt(j));
                if (arrElem == 1) {
                    sumWeight += Integer.parseInt(weights.get(j)); 
                    sumValue += Integer.parseInt(values.get(j));
                }

            }
            if (isMaxValue(sumValue) && isInCapacity(sumWeight)) { 
                finalResult = sumValue + " value, " + sumWeight + " weight";
                bestComb = toBinary(i);
            };

            sumWeight = 0; 
            sumValue = 0;

        }

编辑: 将计算方式更改为:

for (int i = 1; i < combnum; i++) {
            String comb = Integer.toBinaryString(i);
            sumValue = 0;
            sumWeight = 0;
            for (int j = 0; j < comb.length(); j++) {
                if (comb.charAt(j) == '1') {
                    sumValue += itemList.get(j).getValue();
                    sumWeight += itemList.get(j).getWeight();
                }
            }
            if (isMaxValue(sumValue) && isInCapacity(sumWeight)) { 
                maxValue=sumValue;
                maxWeight = sumWeight;
                finalResult = sumValue + " value, " + sumWeight + " weight";
                bestComb = toBinary(i);
            };

对于 2^30 种组合，计时器降至几分钟。干杯。

Answer 1

您的解决方案至少有一个问题:您暴力破解所有可能的配置并检查该配置。唯一的问题是:有许多子问题完全重复，您不需要再次解决。

在这种情况下，我建议您dynamic programming解决这个问题的方法。通俗地说，动态规划是另一种蛮力。您尝试所有可能的解决方案。唯一的区别是它“记住”了旧的子问题结果。你应该看看。