Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.io.BufferedReader;
- import java.io.IOException;
- import java.io.InputStreamReader;
- import java.util.Arrays;
- public class Knapsack2 {
- // value (sum of the values)
- // items minimum weight
- public static long[][] memo = new long[2][100005];
- public static int[] w = new int[105];
- public static int[] v = new int[105];
- public static void main(String[] args) throws IOException
- {
- for (int x = 0; x <= 1; x++)
- Arrays.fill(memo[x], Long.MAX_VALUE);
- memo[0][0] = 0;
- BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
- String[] tmp = in.readLine().split(" ");
- int N = Integer.parseInt(tmp[0]);
- int W = Integer.parseInt(tmp[1]);
- for (int i = 1; i <= N; i++)
- {
- tmp = in.readLine().split(" ");
- w[i] = Integer.parseInt(tmp[0]);
- v[i] = Integer.parseInt(tmp[1]);
- }
- long ans = 0;
- int row = 1, prevRow = 0;
- for (int i = 1; i <= N; i++)
- {
- for (int j = 0; j <= 100000; j++)
- {
- memo[row][j] = memo[prevRow][j];
- if (j-v[i] >= 0)
- memo[row][j] = Math.min(memo[row][j], memo[prevRow][j-v[i]] + w[i]);
- if (memo[row][j] <= W)
- ans = Math.max(ans, j);
- }
- row ^= 1;
- prevRow ^= 1;
- }
- System.out.println(ans);
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement