Solving the knapsack problem with dynamic programming

[Algorithms and data structures for Java programmers](https://www.amazon.co.jp/Java%E3%83%97%E3%83%AD%E3%82%B0%E3%83%A9% E3% 83% 9E% E3% 81% AE% E3% 81% 9F% E3% 82% 81% E3% 81% AE% E3% 82% A2% E3% 83% AB% E3% 82% B4% E3% 83% AA% E3% 82% BA% E3% 83% A0% E3% 81% A8% E3% 83% 87% E3% 83% BC% E3% 82% BF% E6% A7% 8B% E9% 80% A0-% E8% BF% 91% E8% 97% A4-% E5% 98% 89% E9% 9B% AA / dp / 4797326603) is used as a reference. The source code is on GitHub.

import java.util.*;

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

  //An object that represents a knapsack problem
  public Knapsack(int[] size, int[] value) {
    if (size.length != value.length) {
      throw new IllegalArgumentException("'size'When'value'The number of elements does not match");
    }

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

  
  //Put various things in a knapsack of size 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("The size of the knapsack%d%n", m);

    //Put items one by one and seek maximum value from the bottom up
    for (int i = 0; i < N; i++) {

      //Put the item i one by one
      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("goods%d (value%d)Stuff%n", choice[i], value[choice[i]]);
    }
    System.out.printf("Total value= %d%n", total[m]);
  }


  public static void abort(String message) {
    System.err.printf("How to start:java Knapsack size%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("The number of parameters is different.");
    }
    try {
      size = Integer.parseInt(args[0]);
    } catch (NumberFormatException e) {
      abort("Specify a positive integer for the size");
    }
    if (size <= 0) {
      abort("Specify a positive integer for the size");
    }

    knapsack.solve(size);
  }
}

Recommended Posts

Solving the knapsack problem with dynamic programming
[Competition Pro] Solve the knapsack problem with Ruby
Programming with ruby (on the way)
Solving with Ruby, Perl and Java AtCoder ABC 129 C (Part 2) Dynamic programming
[At Coder] Solve the ABC183 D problem with Ruby
[At Coder] Solve the ABC182 D problem with Ruby
Solve the Discrete Logarithm Problem with an arbitrary mod
[Rails] Solving the problem that session timeout does not work
The difference between programming with Ruby classes and programming without it