Advertisement
Guest User

Untitled

a guest
Oct 18th, 2019
100
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.24 KB | None | 0 0
  1. import java.io.BufferedReader;
  2. import java.io.IOException;
  3. import java.io.InputStreamReader;
  4. import java.util.Arrays;
  5.  
  6. public class Knapsack2 {
  7. // value (sum of the values)
  8. // items minimum weight
  9.  
  10. public static long[][] memo = new long[2][100005];
  11. public static int[] w = new int[105];
  12. public static int[] v = new int[105];
  13.  
  14. public static void main(String[] args) throws IOException
  15. {
  16. for (int x = 0; x <= 1; x++)
  17. Arrays.fill(memo[x], Long.MAX_VALUE);
  18. memo[0][0] = 0;
  19. BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
  20. String[] tmp = in.readLine().split(" ");
  21. int N = Integer.parseInt(tmp[0]);
  22. int W = Integer.parseInt(tmp[1]);
  23. for (int i = 1; i <= N; i++)
  24. {
  25. tmp = in.readLine().split(" ");
  26. w[i] = Integer.parseInt(tmp[0]);
  27. v[i] = Integer.parseInt(tmp[1]);
  28. }
  29. long ans = 0;
  30. int row = 1, prevRow = 0;
  31. for (int i = 1; i <= N; i++)
  32. {
  33. for (int j = 0; j <= 100000; j++)
  34. {
  35. memo[row][j] = memo[prevRow][j];
  36. if (j-v[i] >= 0)
  37. memo[row][j] = Math.min(memo[row][j], memo[prevRow][j-v[i]] + w[i]);
  38. if (memo[row][j] <= W)
  39. ans = Math.max(ans, j);
  40. }
  41. row ^= 1;
  42. prevRow ^= 1;
  43. }
  44. System.out.println(ans);
  45. }
  46. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement