BOJ 7579アプリケーション

16112 ワード
テキストリンク

質問する


実行中のアプリケーションでは、再実行のコストと現在使用されているメモリ、および新しいアプリケーションを実行するためにアプリケーションを閉じる最低コストです.
  • を実行するアプリケーション数N<=10
  • 実行するアプリケーションのメモリM<=100000
  • 実行中のアプリケーションを再実行するコストc<=10
  • を実行するアプリケーションのメモリmの和<=10000

    • に近づく


    問題を見ればリュックのような構造だとわかります.
    ではリュックサックについて考えてみます各物品の価値と重量、および限られた重量のバッグを組み込むことができる最大の価値を得る.
    各変数を現在の問題に関連付ける
  • 価値=>実行中のアプリケーションを終了するメモリ
  • 重量=>アプリケーションを終了して再実行するために必要なコスト
    • これは、問題を限られたコストで最大の価値を得ることができることを意味します.
    この方法で問題を解決するには、100 x 100 x 100 x 100のサイズの2次元配列が必要です.100万ですねまた,1つの配列の呼び出し回数は2回であるため,200万の複雑さで問題を解決できる.答えを得るには、0から最大コストのドアを迂回し、その最大値がMを超えるとforドアを閉じて答えを印刷するだけでよいことに注意してください.
    これはリュックサックの問題と似ていますが、最大の価値を追求するのではなく、必要な価値を追求する最低コストなので、近づきにくい問題だと思います.
    リュックサック問題の定式解

    コード#コード#

    import java.io.*;
import java.util.*;

class Pair {
    int m;
    int c;

    Pair(int m, int c) {
        this.m = m;
        this.c = c;
    }
}

class baek__7579 {
    static Pair[] pairs = new Pair[101];
    static int[][] d = new int[100 * 100 + 1][101];

    static int go(int c, int n) {
        if (c <= 0) {
            if (c == 0)
                return 0;
            return -20000000;
        }
        if (n < 0)
            return 0;

        if (d[c][n] != -1)
            return d[c][n];

        d[c][n] = Math.max(go(c - pairs[n].c, n - 1) + pairs[n].m, go(c, n - 1));

        return d[c][n];
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String[] temp = br.readLine().split(" ");
        int n = Integer.parseInt(temp[0]);
        int m = Integer.parseInt(temp[1]);

        temp = br.readLine().split(" ");
        String[] temp1 = br.readLine().split(" ");

        for (int i = 0; i < n; i++) {
            int memory = Integer.parseInt(temp[i]);
            int cost = Integer.parseInt(temp1[i]);
            pairs[i] = new Pair(memory, cost);
        }

        for (int i = 0; i < 100 * 100 + 1; i++) {
            for (int j = 0; j < 101; j++) {
                d[i][j] = -1;
            }
        }

        for (int i = 0; i < 100 * 100 + 1; i++) {
            if (go(i, n - 1) >= m) {
                System.out.print(i);
                return;
            }
        }
    }
}
    Webpack構成babel-loader
    CSS Reset Code