Submission #1254276

#TimeUsernameProblemLanguageResultExecution timeMemory
1254276minhphanKnapsack (NOI18_knapsack)Java
12 / 100
45 ms10592 KiB
import java.io.*; import java.util.*; /** * @since 06.08.2025 */ public final class knapsack { public static void main(String[] args) { Einleser einleser = new Einleser(); int S = einleser.nextInt(); int N = einleser.nextInt(); Map<Integer, Data> datas = new HashMap<>(); for (int i = 0; i < N; i++) { int v = einleser.nextInt(); int w = einleser.nextInt(); int k = einleser.nextInt(); Data data = datas.getOrDefault(w, new Data(w)); data.add(S, v, k); datas.put(w, data); } //Falls zwei Items den gleichen Wert und Gewicht haben, soll ihre Anzahl addiert werden //Falls es praktisch unendlich Items gibt und der Wert am größten ist, sollen //alle andere Items entfernt werden. // int[] dp = new int[S + 1]; dp[0] = 0; for (Data data : datas.values()) { int weight = data.weight; for(DataEntry entry : data.entryList) { int amountUsed = entry.amount; int value = entry.value; if(((long)weight*amountUsed)>=S) {//unbounded knapsack for (int j = weight; j <= S; j++) { dp[j] = Math.max(dp[j], dp[j-weight] + value); } } else { //0-1 knapsack int k = 1; while(amountUsed > 0) { //binary int use = Math.min(k, amountUsed); int currentWeight = weight*use; int currentValue = value*use; for (int j = S - currentWeight; j >= 0; j--) { int newIndex = j + currentWeight; dp[newIndex] = Math.max(dp[newIndex], dp[j] + currentValue); } amountUsed -= k; k <<= 1; } } } } int globalMax = 0; for(int v : dp) { if(v > globalMax) { globalMax = v; } } einleser.write(String.valueOf(globalMax)); einleser.close(); } private static class Data { private final int weight; private int currentAmount; private final SortedSet<DataEntry> entryList; public Data(int weight) { this.weight = weight; this.entryList = new TreeSet<>(); } public void add(int S, int value, int amount) { int maxAmount = S/this.weight; this.entryList.add(new DataEntry(value, amount)); this.currentAmount += amount; if(this.currentAmount > maxAmount) { int removed = this.currentAmount - maxAmount; DataEntry lowestValue = this.entryList.last(); while(removed > 0) { if(removed >= lowestValue.amount) { this.entryList.remove(this.entryList.last()); removed -= lowestValue.amount; lowestValue = this.entryList.last(); } else { lowestValue.amount -= removed; removed = 0; } } } } } private static class DataEntry implements Comparable<DataEntry> { private final int value; private int amount; private DataEntry(int value, int amount) { this.value = value; this.amount = amount; } @Override public int compareTo(DataEntry o) { return -Integer.compare(this.value, o.value); } } private static final class Einleser extends PrintWriter { private final BufferedReader reader; private StringTokenizer tokenizer; public Einleser() { this(System.in, System.out); } public Einleser(InputStream i, OutputStream o) { super(o); reader = new BufferedReader(new InputStreamReader(i)); } public Einleser(String problemName) throws IOException { super(problemName + ".out"); reader = new BufferedReader(new FileReader(problemName + ".in")); } public String next() { try { while (tokenizer == null || !tokenizer.hasMoreTokens()) tokenizer = new StringTokenizer(reader.readLine()); return tokenizer.nextToken(); } catch (Exception e) { } return null; } public int nextInt() { return Integer.parseInt(Objects.requireNonNull(next())); } public double nextDouble() { return Double.parseDouble(Objects.requireNonNull(next())); } public long nextLong() { return Long.parseLong(Objects.requireNonNull(next())); } } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...