ナップサック問題

動的計画法の基礎練。いろいろなパターンのナップサック問題を解く。

基本版

一番オーソドックスなやつ。

重さと価値がwi, viであるN個の品物がある。これらの品物から、重さの総和がWを超えないように選んだときの価値の総和の最大値はいくつか？ただし、各品物は1つずつしかない。(1<=N<=100, 1<=wi,vi<=100, 1<=W<=10000)

i番目までの品物から重さの総和がj以下となるように選んだ場合の価値の総和の最大値をdp[i+1][j]としたとき、

dp[i + 1][j] = dp[i][j] (j < wi)
               max(dp[i][j], dp[i][j - wi] + vi)

が成り立つので、

public class Knapsack1 {

    public static void main(String[] args) {
        int[] w = { 2, 1, 3, 2 };
        int[] v = { 3, 2, 4, 2 };
        int W = 5;
        int N = w.length;

        int[][] dp = new int[N + 1][W + 1];

        for (int i = 0; i < N; i++) {
            for (int j = 0; j <= W; j++) {
                // dp[i+1][j]=i番目までの品物から重さの総和がj以下となるように選んだ場合の最大の価値総和
                if (j < w[i]) {
                    dp[i + 1][j] = dp[i][j];
                } else {
                    dp[i + 1][j] = Math.max(dp[i][j], dp[i][j - w[i]] + v[i]);
                }
            }
        }

        System.out.println(dp[N][W]); // 10
    }
}

計算量はO(NW)

品物を何個でも選べる場合

ぱっと思いつくのは

dp[i + 1][j] = max(dp[i][j - k * wi] + k * vi | k >= 0)

となるもの。プログラムを書くと

public class Knapsack2 {

    public static void main(String[] args) {
        int[] w = { 3, 4, 2 };
        int[] v = { 4, 5, 3 };
        int W = 7;
        int N = w.length;

        int[][] dp = new int[N + 1][W + 1];

        for (int i = 0; i < N; i++) {
            for (int j = 0; j <= W; j++) {
                int max = dp[i][j];
                for (int k = 1; j >= k * w[i]; k++) {
                    max = Math.max(max, dp[i][j - k * w[i]] + k * v[i]);
                }
                dp[i + 1][j] = max;
            }
        }

        System.out.println(dp[N][W]); // 10
    }
}

3重ループがあるので、計算量はO(NW^2)になってしまう。

ループが発生しないように考え直してみると、実はdp[i + 1][j - wi] + viっていうのはi番目の品物をk-1個使った場合の結果に対してさらにもう1個足すという意味が含まれているので、

dp[i + 1][j] = max(dp[i][j - k * wi] + k * vi | k >= 0)
             = max(dp[i][j], dp[i + 1][j - wi] + vi)

と変形できる。これを使ってプログラムを書きなおすと

public class Knapsack2 {

    public static void main(String[] args) {
        int[] w = { 3, 4, 2 };
        int[] v = { 4, 5, 3 };
        int W = 7;
        int N = w.length;

        int[][] dp = new int[N + 1][W + 1];

        for (int i = 0; i < N; i++) {
            for (int j = 0; j <= W; j++) {
                if (j < w[i]) {
                    dp[i + 1][j] = dp[i][j];
                } else {
                    dp[i + 1][j] = Math.max(dp[i][j], dp[i + 1][j - w[i]] + v[i]);
                }
            }
        }

        System.out.println(dp[N][W]); // 10
    }
}

これで計算量はO(NW)となる。

最初のパターンとほんのちょっと違うだけ。

サイズが大きい場合

最初のパターンの制約を

1<=N<=100, 1<=wi<=10^7,1<=vi<=100, 1<=W<=10^7

に変えた場合、O(NW)では厳しい。発想の転換が必要。

今まで重さに対する最大の価値をDPで計算していたが、今回は(サイズの制約がゆるい)価値に対する最小の重みをDPで計算することとする。最終的にはDPの結果がWを超えない最大の価値を出力するようにすれば良い。

i番目までの品物から価値の総和がj以下となるように選んだ場合の重さの総和の最小値をdp[i + 1][j]としたとき、

dp[i + 1][j] = dp[i][j] (j < vi)
               min(dp[i][j], dp[i][j - vi] + wi)

が成り立つ。プログラムで書くと

import java.util.Arrays;

public class Knapsack3 {

    public static void main(String[] args) {
        int[] w = { 2, 1, 3, 2 };
        int[] v = { 3, 2, 4, 2 };
        int W = 5;
        int N = w.length;
        int V = 4; // viの取りうる最大値

        int[][] dp = new int[N + 1][W * V + 1];
        Arrays.fill(dp[0], Integer.MAX_VALUE); // 解が存在しない場合はInteger.MAX_VALUEに
        dp[0][0] = 0;

        for (int i = 0; i < N; i++) {
            for (int j = 0; j <= N * V; j++) {
                // dp[i+1][j]=i番目までの品物から価値の総和がj以下となるように選んだ場合の重さの総和の最小値
                if (j < v[i]) {
                    dp[i + 1][j] = dp[i][j];
                } else {
                    // i-1番目までの品物から価値の総和がjとなるように選ぶ
                    // またはi-1番目の品物から価値の総和がj-viとなるように選び、i番目の品物を加える
                    dp[i + 1][j] = (int) Math.min((long) dp[i][j],
                            (long) dp[i][j - v[i]] + w[i]); // オーバーフロー対策
                }
            }
        }

        int max = 0;
        for (int j = 0; j <= N * V; j++) {
            if (dp[N][j] <= W) {
                max = j; // dp[N][j]がWを超えない最大のjが解
            }
        }
        System.out.println(max); // 7
    }
}

計算量はO(NΣvi)で済む。

選ぶ品物の個数に制約がある場合

続く。

IK.AM