java - 查找前 k 个背包

Question

我得到了背包问题的一个特例，其中权重等于值。我的目标是使用 DP 方法打印j最封闭的解决方案W（目标重量）。

到目前为止，我可以打印一个结果，但我不知道如何有效地跟踪顶级j解决方案。

package com.gazman.quadratic_sieve.core.poly;

import java.util.ArrayList;
import java.util.List;

class Knapsack {

    static List<Integer> knapSack(int W, int[] weights) {
        int i, w;
        int n = weights.length + 1;
        int[][] k = new int[n][W + 1];
        for (i = 0; i < n; i++) {
            for (w = 0; w <= W; w++) {
                if (i == 0 || w == 0) {
                    k[i][w] = 0;
                }
                else {
                    int r = k[i - 1][w];
                    if (weights[i - 1] <= w) {
                        int l = weights[i - 1] + k[i - 1][w - weights[i - 1]];
                        k[i][w] = Math.max(l, r);
                    } else {
                        k[i][w] = r;
                    }
                }
            }
        }

        int res = k[n - 1][W];

        w = W;

        List<Integer> result = new ArrayList<>();

        for (i = n - 1; i > 0 && res > 0; i--) {
            if (res != k[i - 1][w]) {
                result.add(weights[i - 1]);
                res = res - weights[i - 1];
                w = w - weights[i - 1];
            }
        }
        return result;
    }

    public static void main(String[] args) {
        int[] val = new int[]{12, 102, 120, 280, 1000, 1200};
        int W = 1279;
        System.out.println(knapSack(W, val)); // [1000, 120, 102, 12]
    }
}

标签： javaalgorithmknapsack-problem