oj.uz

Submission #645902

# Submission time Handle Problem Language Result Execution time Memory
645902 2022-09-28T09:06:11 Z ateacode Knapsack (NOI18_knapsack) Java 11
37 / 100
 1000 ms 11512 KB 
import java.util.Arrays;
import java.util.Scanner;

class knapsack {
	public static void main(String[] args) {
		// maximal weight of S kg's
		// n items to choose from, each with a value v and quantity q.
		// complete search problem
		// two decisions for each item: 1. Put item in basket 2. Ignore item. Goal is to maximise value.
		// Suppose we know the maximum value for the subset of items n[0..i] 
		// We can figure out max value of subset of items n[0..i+1] because for the marginal
		// decision (do i put item i + 1 in basket), we can update the max value given the optimal decision.
		Scanner in = new Scanner(System.in);

		int maxWeight = in.nextInt();
		int numItems = in.nextInt();

		int[] values = new int[numItems]; 
		int[] weights = new int[numItems];
		int[] quantities = new int[numItems];
		
		for(int i = 0; i < numItems; ++i) {
			values[i] = in.nextInt();
			weights[i] = in.nextInt();
			quantities[i] = in.nextInt();
		}


		int[] maxValueGivenWeight = new int[maxWeight + 1];

		for(int i = 0; i < numItems; ++i) {
		       for(int q = 0; q < quantities[i]; ++q) {	
				// consider the subset of items from 0..i
				for(int curWeight = maxWeight; curWeight >= 0; --curWeight) {
					if(weights[i] <= curWeight) { 
						maxValueGivenWeight[curWeight] = Math.max(
								maxValueGivenWeight[curWeight],
							       	values[i] + maxValueGivenWeight[curWeight - weights[i]]
						);	
					}
				}
		       }
		}

		System.out.println(maxValueGivenWeight[maxWeight]);
	}
}

Subtask #1
0 / 12.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1043 ms 11400 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 11040 KB Output is correct
2 Correct 137 ms 11436 KB Output is correct
3 Correct 137 ms 11396 KB Output is correct
4 Correct 150 ms 11096 KB Output is correct
5 Correct 132 ms 11456 KB Output is correct
6 Correct 137 ms 11244 KB Output is correct
7 Correct 136 ms 11132 KB Output is correct
8 Correct 138 ms 11304 KB Output is correct
9 Correct 160 ms 11164 KB Output is correct
10 Correct 136 ms 11316 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 11040 KB Output is correct
2 Correct 137 ms 11436 KB Output is correct
3 Correct 137 ms 11396 KB Output is correct
4 Correct 150 ms 11096 KB Output is correct
5 Correct 132 ms 11456 KB Output is correct
6 Correct 137 ms 11244 KB Output is correct
7 Correct 136 ms 11132 KB Output is correct
8 Correct 138 ms 11304 KB Output is correct
9 Correct 160 ms 11164 KB Output is correct
10 Correct 136 ms 11316 KB Output is correct
11 Correct 128 ms 10948 KB Output is correct
12 Correct 143 ms 11460 KB Output is correct
13 Correct 138 ms 11244 KB Output is correct
14 Correct 135 ms 11512 KB Output is correct
15 Correct 138 ms 11380 KB Output is correct
16 Correct 150 ms 11208 KB Output is correct
17 Correct 132 ms 11360 KB Output is correct
18 Correct 131 ms 11260 KB Output is correct
19 Correct 134 ms 11312 KB Output is correct
20 Correct 144 ms 11248 KB Output is correct

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1043 ms 11400 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1043 ms 11400 KB Time limit exceeded
2 Halted 0 ms 0 KB -