Submission #623008

#TimeUsernameProblemLanguageResultExecution timeMemory
623008coderInTrainingKnapsack (NOI18_knapsack)Java
73 / 100
1081 ms24924 KiB
import java.util.*; public class knapsack { public static void main (String[]args) { Scanner scan = new Scanner (System.in); int maxWeight = scan.nextInt(); int itemNumber = scan.nextInt(); Hashtable <Integer, ArrayList<Pair>> itemHash = new Hashtable <Integer, ArrayList<Pair>>(); Triplet [] arr = new Triplet [itemNumber]; for (int i = 0; i < itemNumber; i++) { int value = scan.nextInt(); int weight = scan.nextInt(); int copyNumber = scan.nextInt(); Triplet addingTriplet = new Triplet (value, weight, copyNumber); arr[i] = addingTriplet; } Arrays.sort(arr); for (int i = 0; i < itemNumber; i++) { Triplet t = arr[i]; int value = t.value; int weight = t.weight; int copyNumber = t.copyNumber; Pair addingPair = new Pair (value, copyNumber); if (itemHash.containsKey(weight) == false) { itemHash.put(weight, new ArrayList<Pair>()); } itemHash.get(weight).add(addingPair); } Enumeration<Integer> keys = itemHash.keys(); ArrayList<Integer> weights = new ArrayList<Integer>(); while (keys.hasMoreElements()) { int curWeight = keys.nextElement(); weights.add(curWeight); ArrayList<Pair> temp = itemHash.get(curWeight); Collections.sort(temp); itemHash.put(curWeight, temp); } Collections.sort(weights); /* for (int i = 0; i < weights.size(); i++) { ArrayList<Pair> temp = itemHash.get(weights.get(i)); System.out.println(weights.get(i) + ":"); for (int j = 0; j < temp.size(); j++) { System.out.print("(" + temp.get(j).value + ", " + temp.get(j).copyNumber + ") "); } System.out.println(""); } */ // Program works so far // Dp represents the maximum possible value if we have gone through the first i weight groups and have reached a total weight of j long [][] dp = new long [itemHash.size() + 1][maxWeight + 1]; // Initialization for (int i = 0; i <= itemHash.size(); i++) { Arrays.fill(dp[i], Integer.MIN_VALUE); } // Base Case dp[0][0] = 0; // Gone through counter weight groups for (int i = 0; i < weights.size(); i++) { int curWeight = weights.get(i); ArrayList<Pair> valueCopyNumberList = itemHash.get(curWeight); // Reached a current total weight of j for (int j = 0; j <= maxWeight; j++) { int amountLeft = maxWeight - j; // Checks if the state has been reached or not if (dp[i][j] == Integer.MIN_VALUE) { continue; } // Before going through the list, create a transition that skips over this entire weight group dp[i + 1][j] = Math.max(dp[i + 1][j], dp[i][j]); int runningTotal = 0; long addingTotal = 0; boolean finished = false; // Iterate through the weight group for (int k = 0; k < valueCopyNumberList.size(); k++) { int curAddingValue = valueCopyNumberList.get(k).value; int copyNumber = valueCopyNumberList.get(k).copyNumber; for (int l = 0; l < copyNumber; l++) { runningTotal += curWeight; addingTotal += curAddingValue; if (runningTotal > amountLeft) { finished = true; break; } // First transition (Finish the weight group right after adding the current value) dp[i + 1][j + runningTotal] = Math.max(dp[i + 1][j + runningTotal], dp[i][j] + addingTotal); } if (finished) { break; } } } } /* for (int i = 0; i <= itemHash.size(); i++) { for (int j = 0; j <= maxWeight; j++) { if (dp[i][j] == Integer.MIN_VALUE) { System.out.print("- "); continue; } System.out.print(dp[i][j] + " "); } System.out.println(""); } */ long answer = 0; for (int i = 0; i <= maxWeight; i++) { answer = Math.max(answer, dp[itemHash.size()][i]); } System.out.println(answer); } private static class Triplet implements Comparable <Triplet> { int value; int weight; int copyNumber; public Triplet (int value, int weight, int copyNumber) { this.value = value; this.weight = weight; this.copyNumber = copyNumber; } public int compareTo (Triplet t) { return (weight - t.weight); } } private static class Pair implements Comparable <Pair> { int value; int copyNumber; public Pair (int value, int copyNumber) { this.value = value; this.copyNumber = copyNumber; } public int compareTo (Pair p) { return (p.value - value); } } }
#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...