4
2

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 5 years have passed since last update.

動的計画法でナップザック問題を解く

Posted at

Javaプログラマのためのアルゴリズムとデータ構造を参考にしています。
ソースコードはGitHubにあげています。

import java.util.*;

public class Knapsack {
  int[] size;
  int[] value;
  int N;

  // ナップザック問題を表すオブジェクト
  public Knapsack(int[] size, int[] value) {
    if (size.length != value.length) {
      throw new IllegalArgumentException("'size'と'value'の要素数が一致していません");
    }

    this.N = size.length;
    this.size = (int[])size.clone();
    this.value = (int[])value.clone();
  }


  // 大きさmのナップザックに色々入れていく
  public void solve(int m) {
    int[] total = new int[m+1];
    int[] choice = new int[m+1];
    Arrays.fill(choice, -1);
    int repackTotal;
    System.out.printf("ナップザックの大きさは%d%n", m);

    // 品物を1つずつ入れて、ボトムアップ的に最大価値を求める
    for (int i = 0; i < N; i++) {

      // 品物iを一箇所ずつ入れていく
      for (int j = size[i]; j <= m; j++) {
        repackTotal = total[j - size[i]] + value[i];
        if (repackTotal > total[j]) {
          total[j] = repackTotal;
          choice[j] = i;
        }
      }

      System.out.printf("i = %d%n", i);
      System.out.printf("total = ");
      for (int j = 0; j <= m; j++) {
        System.out.printf("%4d", total[j]);
      }
      System.out.printf("%nchoice = ");
      for (int j = 0; j <= m; j++) {
        System.out.printf("%4d", choice[j]);
      }
      System.out.printf("\n");
    }

    for (int i = m; choice[i] >= 0; i -= size[choice[i]]) {
      System.out.printf("品物 %d (価値 %d) を詰め込む %n", choice[i], value[choice[i]]);
    }
    System.out.printf("価値の合計 = %d%n", total[m]);
  }


  public static void abort(String message) {
    System.err.printf("起動法: java Knapsack 大きさ%n");
    System.err.printf("%s%n", message);
    System.exit(1);
  }


  public static void main(String args[]) {
    Knapsack knapsack = new Knapsack(
      new int[] {2, 3, 5, 7, 9},
      new int[] {2, 4, 7, 11, 14}
    );

    int size = 0;
    if (args.length != 1) {
      abort("パラメータの個数が違います。");
    }
    try {
      size = Integer.parseInt(args[0]);
    } catch (NumberFormatException e) {
      abort("大きさには正の整数を指定してください");
    }
    if (size <= 0) {
      abort("大きさには正の整数を指定してください");
    }

    knapsack.solve(size);
  }
}

4
2
2

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
4
2

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?