問題を解く

これはリュックサック問題アルゴリズムで解くことができる問題です.
アプリケーションが消費するメモリ容量がAIA i}Aiに必要なコストがCic i}Ciであれば、メモリ容量M以上を確保するには最小限のコストが必要となる.
したがって、バックパックの問題を処理する際に必要な費用はバックパックのサイズであり、そのバックパックサイズの価値リストとして利用できるのがアプリケーションごとのメモリ容量である.
すなわち、dp配列および点火式は、
d[i][j]-iは、現在確認中のアプリケーションのインデックスであり、アプリケーションを終了し、アプリケーションを終了しない、または両方のいずれかである.jは、必要とされる可能性のある残りの費用である.
ではd[i]=Max(d[i]+Ai,d[i]][j])d[i]=Max(d[i-C i]+A i},d[i-1][j])d[i]=Max
次の例では、dpスキーマテーブルを次のように描画します.
5 6
3 1 2 3 4
3 0 3 5 4

少なくとも6個のメモリが必要な場合、コストの最小値はテーブルの結果値に基づいて6になります.

質問リンク

boj/7579

ソースコード

PS/2096 .java

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

class Main {

  static int[][] arr = new int[101][2];
  static int[][] d = new int[101][10001];
  static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

  public static void main(String[] args) throws Exception {
    StringTokenizer st = new StringTokenizer(br.readLine());
    int n = Integer.parseInt(st.nextToken());
    int m = Integer.parseInt(st.nextToken());
    st = new StringTokenizer(br.readLine());
    int sum = 0;
    int ans = 10000001;
    for (int i = 1; i <= n; i++) {
      arr[i][0] = Integer.parseInt(st.nextToken());

    }
    st = new StringTokenizer(br.readLine());
    for (int i = 1; i <= n; i++) {
      arr[i][1] = Integer.parseInt(st.nextToken());
      sum += arr[i][1];
    }
    for (int i = 1; i <= n; i++) {
      for (int j = 0; j <= sum; j++) {
        if (j - arr[i][1] >= 0) {
          d[i][j] = Math.max(d[i - 1][j - arr[i][1]] + arr[i][0], d[i - 1][j]);
        } else {
          d[i][j] = d[i - 1][j];
        }
        if (d[i][j] >= m) {
          ans = Math.min(ans, j);
        }
      }
    }
    System.out.println(ans);
  }
}