---
title: ナップサック問題
tags: []
categories: ["Programming", "Algorithm", "DynamicProgramming", "Knapsack"]
date: 2011-07-24T12:01:57Z
updated: 2011-07-24T12:01:57Z
---

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

### 基本版

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

> 重さと価値が`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)で済む。

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

続く。