public class ClassicProblem {
final int N = 80; // Max number of objects, Max weight
long[] dp;
public long maximalValue(int[] cnt, int[] w, int[] v, int limit)
{
int n = cnt.length;
long ret = 0;
// First we sort them by (value / weight), from small to large
for(int iteration = 1; iteration <= n; iteration ++)
for(int i = 0; i < n-1; i++)
if((long) v[i] * w[i+1] > (long) v[i+1] * w[i])
{
int t = w[i]; w[i] = w[i+1]; w[i+1] = t;
t = v[i]; v[i] = v[i+1]; v[i+1] = t;
t = cnt[i]; cnt[i] = cnt[i+1]; cnt[i+1] = t;
}
int M = N * N * N;
dp = new long[M+1];
for(int i = 1; i <= M; i++)
dp[i] = -1000000000000000000L;
// take < M of {0 .. i-1}, take some i, take all of {i+1 .. n}
for(int i = 0; i < n; i++)
{
int s
= Math.
min(N, cnt
[i
]); for(int j = 1; ; j *= 2)
{
for(int k = M; k >= x * w[i]; k--)
dp
[k
] = Math.
max(dp
[k
], dp
[k
-x
*w
[i
]] + 1L
*v
[i
]*x
); s -= x;
if(s == 0)
break;
}
}
for(int i
= 0; i
<= Math.
min(M, limit
); i
++) {
int remain = limit - i;
long cur = dp[i];
for(int j = n-1; j >= 0; j--)
{
int take
= Math.
min(remain
/ w
[j
], cnt
[j
] - Math.
min(cnt
[j
], N
)); remain -= w[j] * take;
cur += (long)v[j] * take;
}
ret
= Math.
max(ret, cur
); }
return ret;
}
}
cHVibGljIGNsYXNzIENsYXNzaWNQcm9ibGVtIHsKCiAgICBmaW5hbCBpbnQgTiA9IDgwOyAvLyBNYXggbnVtYmVyIG9mIG9iamVjdHMsIE1heCB3ZWlnaHQKICAgIGxvbmdbXSBkcDsKCiAgICBwdWJsaWMgbG9uZyBtYXhpbWFsVmFsdWUoaW50W10gY250LCBpbnRbXSB3LCBpbnRbXSB2LCBpbnQgbGltaXQpCiAgICB7CiAgICAgICAgaW50IG4gPSBjbnQubGVuZ3RoOwogICAgICAgIGxvbmcgcmV0ID0gMDsKCiAgICAgICAgLy8gRmlyc3Qgd2Ugc29ydCB0aGVtIGJ5ICh2YWx1ZSAvIHdlaWdodCksIGZyb20gc21hbGwgdG8gbGFyZ2UKICAgICAgICBmb3IoaW50IGl0ZXJhdGlvbiA9IDE7IGl0ZXJhdGlvbiA8PSBuOyBpdGVyYXRpb24gKyspCiAgICAgICAgICAgIGZvcihpbnQgaSA9IDA7IGkgPCBuLTE7IGkrKykKICAgICAgICAgICAgICAgIGlmKChsb25nKSB2W2ldICogd1tpKzFdID4gKGxvbmcpIHZbaSsxXSAqIHdbaV0pCiAgICAgICAgICAgICAgICB7CiAgICAgICAgICAgICAgICAgICAgaW50IHQgPSB3W2ldOyB3W2ldID0gd1tpKzFdOyB3W2krMV0gPSB0OwogICAgICAgICAgICAgICAgICAgIHQgPSB2W2ldOyB2W2ldID0gdltpKzFdOyB2W2krMV0gPSB0OwogICAgICAgICAgICAgICAgICAgIHQgPSBjbnRbaV07IGNudFtpXSA9IGNudFtpKzFdOyBjbnRbaSsxXSA9IHQ7CiAgICAgICAgICAgICAgICB9CgogICAgICAgIGludCBNID0gTiAqIE4gKiBOOwogICAgICAgIGRwID0gbmV3IGxvbmdbTSsxXTsKICAgICAgICBmb3IoaW50IGkgPSAxOyBpIDw9IE07IGkrKykKICAgICAgICAgICAgZHBbaV0gPSAtMTAwMDAwMDAwMDAwMDAwMDAwMEw7CiAgICAgICAgLy8gdGFrZSA8IE0gb2YgezAgLi4gaS0xfSwgdGFrZSBzb21lIGksIHRha2UgYWxsIG9mIHtpKzEgLi4gbn0KICAgICAgICBmb3IoaW50IGkgPSAwOyBpIDwgbjsgaSsrKQogICAgICAgIHsKICAgICAgICAgICAgaW50IHMgPSBNYXRoLm1pbihOLCBjbnRbaV0pOwogICAgICAgICAgICBmb3IoaW50IGogPSAxOyA7IGogKj0gMikKICAgICAgICAgICAgewogICAgICAgICAgICAgICAgaW50IHggPSBNYXRoLm1pbihzLCBqKTsKICAgICAgICAgICAgICAgIGZvcihpbnQgayA9IE07IGsgPj0geCAqIHdbaV07IGstLSkKICAgICAgICAgICAgICAgICAgICBkcFtrXSA9IE1hdGgubWF4KGRwW2tdLCBkcFtrLXgqd1tpXV0gKyAxTCp2W2ldKngpOwogICAgICAgICAgICAgICAgcyAtPSB4OwogICAgICAgICAgICAgICAgaWYocyA9PSAwKQogICAgICAgICAgICAgICAgICAgIGJyZWFrOwogICAgICAgICAgICB9CiAgICAgICAgfQoKICAgICAgICBmb3IoaW50IGkgPSAwOyBpIDw9IE1hdGgubWluKE0sIGxpbWl0KTsgaSsrKQogICAgICAgIHsKICAgICAgICAgICAgaW50IHJlbWFpbiA9IGxpbWl0IC0gaTsKICAgICAgICAgICAgbG9uZyBjdXIgPSBkcFtpXTsKICAgICAgICAgICAgZm9yKGludCBqID0gbi0xOyBqID49IDA7IGotLSkKICAgICAgICAgICAgewogICAgICAgICAgICAgICAgaW50IHRha2UgPSBNYXRoLm1pbihyZW1haW4gLyB3W2pdLCBjbnRbal0gLSBNYXRoLm1pbihjbnRbal0sIE4pKTsKICAgICAgICAgICAgICAgIHJlbWFpbiAtPSB3W2pdICogdGFrZTsKICAgICAgICAgICAgICAgIGN1ciArPSAobG9uZyl2W2pdICogdGFrZTsKICAgICAgICAgICAgfQogICAgICAgICAgICByZXQgPSBNYXRoLm1heChyZXQsIGN1cik7CiAgICAgICAgfQogICAgICAgIHJldHVybiByZXQ7CiAgICB9Cgp9Cg==