제출 #1237276

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1237276		kamran0708	Knapsack (NOI18_knapsack)	Java	73 / 100	807 ms	327680 KiB

knapsack

import java.util.*;

public class knapsack {

    static int n, s;
    static int[][] item;          // {value, weight, count}
    static int[][] dp;            // memo idx×currWt, -1 = unvisited

    static int solve(int idx, int currWt) {
        if (currWt > s)  return Integer.MIN_VALUE;  // overweight
        if (idx == n)    return 0;                  // no more items
        if (dp[idx][currWt] != -1) return dp[idx][currWt];

        int best = 0;
        int v = item[idx][0];
        int w = item[idx][1];
        int c = item[idx][2];

        // try taking t copies, 0 … c
        for (int t = 0; t <= c && currWt + t * w <= s; t++) {
            int candidate = t * v + solve(idx + 1, currWt + t * w);
            best = Math.max(best, candidate);
        }
        return dp[idx][currWt] = best;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        s = sc.nextInt();              // capacity
        n = sc.nextInt();              // item types
        item = new int[n][3];
        for (int i = 0; i < n; i++) {
            item[i][0] = sc.nextInt(); // value
            item[i][1] = sc.nextInt(); // weight
            item[i][2] = sc.nextInt(); // count
        }

        dp = new int[n][s + 1];
        for (int[] row : dp) Arrays.fill(row, -1);

        System.out.println(solve(0, 0));
    }
}

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