提出詳細
ソースコード
import java.util.Scanner;
public class Main_DP {
int n, budget;
int[] budgets;
int[] sizes;
Set[][] dp;
Main_DP() {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
budget = sc.nextInt();
dp = new Set[n+1][budget+1];
budgets = new int[n+1];
sizes = new int[n+1];
for (int i = 1; i <= n; i++) {
int price = sc.nextInt();
int size = sc.nextInt();
budgets[i] = price;
sizes[i] = size;
}
}
Set getResult() {
return calc(n, budget);
}
static int count;
Set calc(int num, int budget) {
if(dp[num][budget] != null)
return dp[num][budget];
if (num == 0) {
return new Set(this.budget - budget, 0);
} else if (budget < budgets[num]) {
return dp[num][budget] = new Set(calc(num-1, budget));
} else {
Set set1 = new Set(calc(num-1, budget));
Set set2 = new Set(calc(num-1, budget - budgets[num]));
set2.size += sizes[num];
dp[num][budget] = set1.size > set2.size ? set1 : set2;
return dp[num][budget];
}
}
public static void main(String[] args) {
Set result = new Main_DP().getResult();
System.out.println(result.price + " " + result.size);
}
class Set {
public Set(Set set) {
this.price = set.price;
this.size = set.size;
}
public Set(int price, int size) {
this.price = price;
this.size = size;
}
long price;
long size;
}
}
提出情報
提出出力結果
テストケース情報
京都産業大学コンピュータ理工学部