Submission #955610

#	Time	Username	Problem	Language	Result	Execution time	Memory
955610		UCSBl	Knapsack (NOI18_knapsack)	Java	73 / 100	832 ms	262144 KiB

knapsack

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class knapsack {
	public static void main (String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int S = Integer.parseInt(st.nextToken());
		int N = Integer.parseInt(st.nextToken());
		
		long[][] dp = new long[N+1][S+1];
		
		// dp(i, j) = using the first i weights, with an upper bound of j capacity - what is the best
		// price
		
		long[][] items = new long[N+1][3];
		
		for (int i = 1; i <= N; i++) {
			st = new StringTokenizer(br.readLine());
			items[i][0] = Long.parseLong(st.nextToken());
			items[i][1] = Long.parseLong(st.nextToken());
			items[i][2] = Long.parseLong(st.nextToken());
		}
		
		for (int i = 1; i <= N; i++) {
			long pi = items[i][0];
			long wi = items[i][1];
			long ki = items[i][2];
			
			for (int j = 1; j <= S; j++) {
				for (int k = 0; k <= j/((int)wi) && k <= ((int) ki); k++) {
					dp[i][j] = Math.max(Math.max(dp[i][j], dp[i-1][j]), 
										dp[i-1][j-k*((int)wi)] + pi*((long) k));
				}
			}
		}
		
		System.out.println(dp[N][S]);
		
	}
}

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