USACO 2018 Open: Talent Show

USACO 2018 Open Talent Show

In Short

Given N objects with value Vi and weight Wi, a collection of elements is said to have total value-to-weight ratio as (the sum of their value) divided by (the sum of their weight). Find the best possible value-to-weight ratio of these X objects, given the restraint that the collection must have total weight at least W.
Return that ratio multiplied by 1000 and floored.

Analysis

It would be very difficult to calculate this optimal ratio - we'd have to either

1. try all possible collections - O(2^n), where n is at most 250, about 10 to the power of 75 calculations, OR
2. use a greedy heuristic - get the objects with the best ratio until it satisfies the weight limit.

Neither of those are too to our liking, so how about searching for it?

The search space is linear and not infinite - it asks for the ratio to the closest thousandths.

The search space is sorted as well - if ratio X is achievable, then ratio Y < X is also achievable, if ratio A is impossible, then ratio   B > A is also impossible.

This only means one thing - binary search!

Binary Search

Every binary search is accompanied by some function that reports if a value in the search space is achievable or impossible.

It's much, much easier to verify if a ratio, K, is achievable, than finding out directly what K is.

So let's make a new problem.

Binary Search Problem - Achievable or Impossible?

Given N objects with value Vi and weight Wi, a restraint W, and a ratio K, find if there exists a sequence X where

for all integers i between 1 and N inclusive such that:

We can convert this formula into:

Let's sort the objects by  so that the first will be the object with the greatest . Then, we pick (set the Xi value to 1) all objects with a positive .

However, we overlooked the restraint. When, after picking all positive values, the total weight of all objects are more than the restraint, we can skip that part. 

To find out whether or not we can satisfy the weight restraint when the current total weight is less than the restraint, we turn to a variant of 0/1 knapsack.

This is nearly the same as the 0/1 knapsack problem, except for one thing that's different - the restraint is a lower bound (the minimum total weight), not an upper bound (the size of the knapsack).

The standard 0/1 knapsack recurrence equation for an object i and an lower bound j is like so:

or

but when there is an upper bound instead, we update values ahead of us, not behind:

or

We want to know the maximum possible value with weight above W, so that is .

Here's the code judging if the ratio K is doable or not.

bool doable(double k)

{

K = k;

sort(cows, cows+N);

double A1 = 0;

int tW = 0, i = 0;

while((cows[i].t - cows[i].w*K) >= 0)

{

A1 += (cows[i].t - cows[i].w*K);

tW += cows[i].w;

i++;

}

if(tW >= W) return true;

memset(knaps, 254, sizeof knaps);

knaps[tW] = A1;

for(; i<N; i++)

for(int j=W-1; j >= tW; j--)

{

int q = (j + cows[i].w > W) ? W : j + cows[i].w;

knaps[q] = max(knaps[q], knaps[j] + cows[i].t - cows[i].w * K);

}

return knaps[W] >= 0;

}

NOTICE that the function judged K in two parts.