| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1254272 | minhphan | Knapsack (NOI18_knapsack) | Java | 0 ms | 0 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.getLast();
while(removed > 0) {
if(removed >= lowestValue.amount) {
this.entryList.removeLast();
removed -= lowestValue.amount;
lowestValue = this.entryList.getLast();
} 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()));
}
}
}