リュックサック問題の出力最適案

一般的に、リュックサック問題は最適解を要求し、この最適値を出力するスキームを要求する場合は、一般的な動的計画問題出力スキームの方法を参照することができる:各状態の最適値が状態遷移方程式のいずれから推定されたかを記録する、すなわち、どの決定から推定されたかを記録することで、この決定に基づいて前の状態を見つけることができる.前の状態から前に進めばよいが、ここでは0-1リュックサックを例に、以下のような入力が与えられる.

c = [2,3,4,5,6,7,8];
v = [3,4,5,6,7,8,9];
V = 23;

最適値を解く状態遷移方程式は,d p[i][j]=m a x{d p[i−1][j],d p[i−1][j−c[i]+v[i]}dp[i]=max{dp[i−1][j],dp[i−1][j−c[i]+v[i]}dp[i][j]=max{dp[i−1][j],dp[i−1][j−c[i]+v[i]}である.さらに1つの配列g[i][j]g[i][j]g[i][j]を用いて、g[i][j]=0 g[i][j]=0 g[i][j]=0としてd p[i][j]dp[i][j]dp[i][j]dp[i][j]を押し出した値を表すと、方程式の前項が用いられ、g[i][j]=1 g[i][j]=1 g[i][j]=1 g[i][j]=1は、方程式を用いた後項を表す.

    public int knapsackProblem(int[] c, int[] v, int cap) {
        int[][] dp = new int[c.length + 1][cap + 1], g = new int[c.length + 1][cap + 1];
        List<Integer> list = new LinkedList<>();
        for (int i = 1; i <= c.length; i++) {
            for (int j = cap; j > 0; j--) {
                if (c[i - 1] <= j) {
                    if (dp[i - 1][j] >= dp[i - 1][j - c[i - 1]] + v[i - 1]) {
                        dp[i][j] = dp[i - 1][j];
                        g[i][j] = 0;
                    } else {
                        dp[i][j] = dp[i - 1][j - c[i - 1]] + v[i - 1];
                        g[i][j] = 1;
                    }
                } else {
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }
        int i = c.length, V = cap;
        while (i > 0) {
            if (g[i][V] == 0) {
                i--;
            } else {
                list.add(i - 1);
                V -= c[i-- - 1];
            }
        }
        Collections.reverse(list);
        System.out.println("       ： " + list);
        return dp[c.length][cap];
    }

下一篇:バックパック问题の组み合わせバックパック问题下一篇:バックパック问题の最优秀方案総数