Submission #900187

#	Time	Username	Problem	Language	Result	Execution time	Memory
900187		jkwn	Knapsack (NOI18_knapsack)	Java	73 / 100	484 ms	262144 KiB

knapsack

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

public class knapsack {
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer tokenizer = new StringTokenizer(in.readLine());

        int s = Integer.parseInt(tokenizer.nextToken());
        int n = Integer.parseInt(tokenizer.nextToken());
        item[] items = new item[n+1];
        int[][] dp = new int[s+1][n+1];
        dp[0][0] = 1;

        for (int i = 1; i < n+1; i++) {
            tokenizer = new StringTokenizer(in.readLine());
            items[i] = new item(Integer.parseInt(tokenizer.nextToken()),Integer.parseInt(tokenizer.nextToken()),Integer.parseInt(tokenizer.nextToken()));
        }

//        for (int i = 0; i < n; i++) {
//            int v = items[i+1].v;
//            int w = items[i+1].w;
//            int k = items[i+1].k;
//            for (int j = 0; j < s+1; j++) {
//                if (dp[i][j] >= 0) {
//                    for (int count = 0; count <= k; count++) {
//                        if (j + w * count <= s) {
//                            dp[i+1][j+w*count] = Math.max(dp[i+1][j+w*count], dp[i][j] + v*count);
//                        }
//                        else {
//                            break;
//                        }
//                    }
//                }
//            }
//        }

        int ans = 0;
        for (int i = 1; i < n+1; i++) {
            int v = items[i].v;
            int w = items[i].w;
            int k = items[i].k;
            for (int j = 0; j < s+1; j++) {
                for (int count = 0; count <= k; count++) {
                    if (j - w * count >= 0) {
//                        if (dp[i-1][j - w * count] >= 1) {
//                            dp[i][j] = Math.max(dp[i][j], dp[i-1][j-w*count] + v * count);
//                            ans = Math.max(ans, dp[i][j]);
//                        }
                        if (dp[j - w * count][i-1] >= 1) {
                            dp[j][i] = Math.max(dp[j][i], dp[j - w * count][i-1] + v * count);
                            ans = Math.max(ans, dp[j][i]);
                        }
                    }
                    else {
                        break;
                    }
                }
            }
        }
        System.out.println(ans-1);
    }
    static class item {
        int v, w, k;
        item(int v, int w, int k) {
            this.v = v;
            this.w = w;
            this.k = k;
        }
    }
}

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