fork download
  1. public class ClassicProblem {
  2.  
  3. final int N = 80; // Max number of objects, Max weight
  4. long[] dp;
  5.  
  6. public long maximalValue(int[] cnt, int[] w, int[] v, int limit)
  7. {
  8. int n = cnt.length;
  9. long ret = 0;
  10.  
  11. // First we sort them by (value / weight), from small to large
  12. for(int iteration = 1; iteration <= n; iteration ++)
  13. for(int i = 0; i < n-1; i++)
  14. if((long) v[i] * w[i+1] > (long) v[i+1] * w[i])
  15. {
  16. int t = w[i]; w[i] = w[i+1]; w[i+1] = t;
  17. t = v[i]; v[i] = v[i+1]; v[i+1] = t;
  18. t = cnt[i]; cnt[i] = cnt[i+1]; cnt[i+1] = t;
  19. }
  20.  
  21. int M = N * N * N;
  22. dp = new long[M+1];
  23. for(int i = 1; i <= M; i++)
  24. dp[i] = -1000000000000000000L;
  25. // take < M of {0 .. i-1}, take some i, take all of {i+1 .. n}
  26. for(int i = 0; i < n; i++)
  27. {
  28. int s = Math.min(N, cnt[i]);
  29. for(int j = 1; ; j *= 2)
  30. {
  31. int x = Math.min(s, j);
  32. for(int k = M; k >= x * w[i]; k--)
  33. dp[k] = Math.max(dp[k], dp[k-x*w[i]] + 1L*v[i]*x);
  34. s -= x;
  35. if(s == 0)
  36. break;
  37. }
  38. }
  39.  
  40. for(int i = 0; i <= Math.min(M, limit); i++)
  41. {
  42. int remain = limit - i;
  43. long cur = dp[i];
  44. for(int j = n-1; j >= 0; j--)
  45. {
  46. int take = Math.min(remain / w[j], cnt[j] - Math.min(cnt[j], N));
  47. remain -= w[j] * take;
  48. cur += (long)v[j] * take;
  49. }
  50. ret = Math.max(ret, cur);
  51. }
  52. return ret;
  53. }
  54.  
  55. }
  56.  
Compilation error #stdin compilation error #stdout 0s 0KB
stdin
Standard input is empty
compilation info
Main.java:1: error: class ClassicProblem is public, should be declared in a file named ClassicProblem.java
public class ClassicProblem {
       ^
1 error
stdout
Standard output is empty