동적설계법 - 배낭문제 0

/**
동적설계법
01 배낭문제(Knapsack problem) - 0

n = 4
(w, v) = {(2,3),(1,2),(3,4),(2,2)}
W = 5
ouput : 7

유명한 배낭 문제이다. 일반적인 방법으로 각 물건에 대해 (넣는다/넣지않는다)로 두 가지 상태로 나눠서 탐색한다.

**/
import java.io.*;
import java.lang.*;
class Main {

  static int W;
  static int[] v;
  static int[] w;
  static int n;
  
  public static void main(String[] args) throws IOException {
    //BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    n = 4;
    w = new int[] {2, 1, 3, 2};
    v = new int[] {3, 2, 4, 2};
    W = 5;

    int res = solve(0,W);
    System.out.println(res);
  }

  
  static int solve(int i, int W) {
    if (i == n) {
      return 0;
    } else if ( W < w[i]) {
      //skip
      return solve(i+1, W);
    } else {
      // 넣지 않는 경우, 넣는 경우 조사.
      int a = solve(i+1, W);
      int b = solve(i + 1, W - w[i]) + v[i];
      return Math.max(a, b);
    }

  }
}