BOJ 17845コース
13159 ワード
質問する
徐允の最大学習時間はNであり、授業ごとに必要な学習時間と重要度は与えられている.最大学習時間内に最大重要度の問題を出力します.最大学習時間1<=N<=10000 科目数1<=K<=1000 に近づくは非常に典型的なリュックサックの問題です. d[N][M]d[N][M]d[N][M]は、0-M第1課で最大N時間かかる最大重要度として定義される. この点火式は、 Mの第1課を聞かないことで確立される. 聞かない場合
d[N][M−1]d[N][M-1]d[N][M−1]
d[N−t[M]][M−1]+v[M]d[N-t[M]][M-1]+v[M]d[N−t[M]][M−1]+v[M] d[N][M]=Math.max(d[N][M−1],d[N−t[M]][M−1]+v[M])d[N][M] = Math.max(d[N][M-1], d[N-t[M]][M-1]+v[M])d[N][M]=Math.max(d[N][M−1],d[N−t[M]][M−1]+v[M])の初期値が混同されている場合は、以下の問題を考慮してください.
実は初期値の設定がよくわかりません n < 0
nが0より小さい場合は、与えられた時間よりも多くの時間がかかることを示し、したがって、すべての値を相殺するのに十分な値である最大科目数xの最大重要度を返す. n == 0
指定した時間に基づいて書かれているため、0を返します. m < 0
指定された科目がないと、どうしてもゼロになります.したがって、0を返します. JAVAコード
徐允の最大学習時間はNであり、授業ごとに必要な学習時間と重要度は与えられている.最大学習時間内に最大重要度の問題を出力します.
d[N][M−1]d[N][M-1]d[N][M−1]
d[N−t[M]][M−1]+v[M]d[N-t[M]][M-1]+v[M]d[N−t[M]][M−1]+v[M]
実は初期値の設定がよくわかりません
nが0より小さい場合は、与えられた時間よりも多くの時間がかかることを示し、したがって、すべての値を相殺するのに十分な値である最大科目数xの最大重要度を返す.
指定した時間に基づいて書かれているため、0を返します.
指定された科目がないと、どうしてもゼロになります.したがって、0を返します.
import java.io.*;
import java.util.*;
class baek__17845 {
static int[][] d = new int[10001][1000];
static int[] v;
static int[] t;
static int go(int n, int k) {
if (n <= 0) {
if (n == 0)
return 0;
return -100000000;
}
if (k < 0)
return 0;
if (d[n][k] != -1)
return d[n][k];
d[n][k] = Math.max(go(n, k - 1), go(n - t[k], k - 1) + v[k]);
return d[n][k];
}
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 k = Integer.parseInt(temp[1]);
v = new int[k];
t = new int[k];
for (int i = 0; i < k; i++) {
temp = br.readLine().split(" ");
v[i] = Integer.parseInt(temp[0]);
t[i] = Integer.parseInt(temp[1]);
}
for (int i = 0; i < n + 1; i++) {
for (int j = 0; j < k; j++) {
d[i][j] = -1;
}
}
System.out.print(go(n, k - 1));
}
}
Reference
この問題について(BOJ 17845コース), 我々は、より多くの情報をここで見つけました https://velog.io/@since-1994/DP-BOJ-17845-수강-과목テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol