# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1136606 | b1t_exe | Knapsack (NOI18_knapsack) | Java | 0 ms | 0 KiB |
import java.util.*;
public class Main {
public static int f(int s, int n, int[][] arr, int i, int[][] memo) {
if (i == n) return 0; // Base case: no items left to process
if (memo[i][s] != -1) return memo[i][s]; // Return cached result
int maxProfit = f(s, n, arr, i + 1, memo); // Skip current item
int v = arr[i][0];
int w = arr[i][1];
int k = arr[i][2];
// Consider taking current item up to its limit
for (int count = 1; count <= k && count * w <= s; count++) {
maxProfit = Math.max(maxProfit, count * v + f(s - count * w, n, arr, i + 1, memo));
}
memo[i][s] = maxProfit; // Cache the result
return maxProfit;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int t = 1; // Number of test cases
while (t-- > 0) {
int x = sc.nextInt(); // Maximum weight capacity
int n = sc.nextInt(); // Number of items
int[][] arr = new int[n][3]; // Item details: value, weight, max quantity
for (int i = 0; i < n; i++) {
arr[i][0] = sc.nextInt(); // Value of item
arr[i][1] = sc.nextInt(); // Weight of item
arr[i][2] = sc.nextInt(); // Maximum quantity of item
}
int[][] memo = new int[n][x + 1];
for (int[] row : memo) Arrays.fill(row, -1);
System.out.println(f(x, n, arr, 0, memo));
}
sc.close();
}
}