Submission #623008

#	Time	Username	Problem	Language	Result	Execution time	Memory
623008		coderInTraining	Knapsack (NOI18_knapsack)	Java	73 / 100	1081 ms	24924 KiB

knapsack

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);
        }
    }
}

• Subtask 1: 12 / 12
• Subtask 2: 17 / 17
• Subtask 3: 20 / 20
• Subtask 4: 24 / 24
• Subtask 5: 0 / 27