Submission #501386

#	Time	Username	Problem	Language	Result	Execution time	Memory
501386		churros	Knapsack (NOI18_knapsack)	Java	0 / 100	1095 ms	9124 KiB

knapsack

import java.io.*;
import java.util.*;

public class knapsack {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter pw = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int maxWeight = Integer.parseInt(st.nextToken());
        int numItemTypes = Integer.parseInt(st.nextToken());
        int[] maxVal = new int[maxWeight + 1];
        int[] itemValue = new int[numItemTypes];
        int[] itemWeight = new int[numItemTypes];
        int[] itemCount = new int[numItemTypes];

        for (int i = 0; i < numItemTypes; i++) {
            st = new StringTokenizer(br.readLine());
            int value = Integer.parseInt(st.nextToken());
            int weight = Integer.parseInt(st.nextToken());
            int count = Integer.parseInt(st.nextToken());
            itemValue[i] = value;
            itemWeight[i] = weight;
            itemCount[i] = count;
        }

        int ret = 0;
        for (int i = 1; i <= (int) Math.pow(2, numItemTypes); i++) {
            int bit = i;
            int value = 0;
            int totalWeight = 0;
            for (int j = 0; j < numItemTypes; j++) {
                if ((bit & 1) == 1) {
                    value += itemValue[j];
                    totalWeight += itemWeight[j];
                }
                bit >>= 1;
                if (bit == 0) {
                    break;
                }
            }
            if (totalWeight <= maxWeight)
                ret = Math.max(ret, value);
        }

        pw.println(ret);

        br.close();
        pw.close();
    }
}

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