fork download
copy 
  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
comments (?)
stdin
copy 
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
copy 
Standard output is empty
https://ideone.com/8DmwsC
language:
Java (12.0.1)
created:
9 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!