| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 719535 | biximo | Knapsack (NOI18_knapsack) | Java | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
import java.util.*;
import java.io.*;
public class knapsack {
static BufferedReader in;
public static void main(String[] args) throws Exception {
in = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer str = new StringTokenizer(in.readLine());
int s = Integer.parseInt(str.nextToken());
int n = Integer.parseInt(str.nextToken());
LinkedList<Integer> keyset = new LinkedList<>();
HashMap<Integer, PriorityQueue<item>> items = new HashMap<>();
for(int i = 0; i < n; i ++) {
str = new StringTokenizer(in.readLine());
item item = new item(Integer.parseInt(str.nextToken()), Integer.parseInt(str.nextToken()), Integer.parseInt(str.nextToken()));
if(!items.containsKey(item.weight)) {
items.put(item.weight, new PriorityQueue<>());
keyset.add(item.weight);
}
items.get(item.weight).add(item);
}
int[] dp = new int[s + 1];
Arrays.fill(dp, -1);
dp[0] = 0;
int max = 0;
while(!keyset.isEmpty()) {
PriorityQueue<item> pqItems = items.get(keyset.poll());
item next = pqItems.poll();
Queue<Integer> processNext = new LinkedList<>();
for(int b = s; b >= 0; b --) {
if(b + next.weight <= s) {
if(dp[b + next.weight] < dp[b] + next.value) {
dp[b + next.weight] = dp[b] + next.value;
processNext.add(b + next.weight);
}
max = Math.max(max, dp[b + next.weight]);
}
}
for(int a = 1; a < next.copies; a ++) {
int times = processNext.size();
if(times == 0)
break;
for(int b = 0; b < times; b ++) {
int ind = processNext.poll();
if(ind + next.weight <= s && dp[ind + next.weight] < dp[ind] + next.value) {
dp[ind + next.weight] = dp[ind] + next.value;
processNext.add(ind + next.weight);
max = Math.max(max, dp[ind + next.weight]);
}
}
}
while(!pqItems.isEmpty()) {
next = pqItems.poll();
int times = -1;
for(int a = 0; a < next.copies; a ++) {
times = processNext.size();
if(times == 0)
break;
for(int b = 0; b < times; b ++) {
int ind = processNext.poll();
if(ind + next.weight <= s && dp[ind + next.weight] < dp[ind] + next.value) {
dp[ind + next.weight] = dp[ind] + next.value;
processNext.add(ind + next.weight);
max = Math.max(max, dp[ind + next.weight]);
}
}
}
if(times == 0)
break;
}
}
System.out.println(max);
}
static class item implements Comparable<item> {
int value, weight, copies;
item(int value, int weight, int copies) {
this.value = value;
this.weight = weight;
this.copies = copies;
}
@Override
public int compareTo(KnapsackNOI.item o) {
return Integer.compare(o.value, this.value);
}
}
}