Knapsack With a Large Budget and Small Benefits
A team must choose a subset of 200 infrastructure projects. Project i has integer cost ci up to 10^9 and integer benefit bi between 1 and 1000. The total budget B is 10^9. Projects are indivisible. A previous engineer implemented a 0/1 knapsack dynamic program with a table of (n+1) x (B+1) entries. It compiles, but the process is killed for using too much memory. A colleague suggests sorting by bi/ci and taking projects greedily until the budget is exhausted. The deadline is tight. The available machine has 256 MB of RAM and a 2 GHz CPU; about 10^8 simple operations take one second. A second variant has n = 40, B = 10^9, and bi up to 10^9, so the benefit sum is also too large for benefit-indexed DP.
1. Explain why the original DP fails and give a correct DP formulation for the first instance, including time and memory.
Read the worked answer
The original table has 201 x (10^9 + 1) entries. Even at one byte per entry that is about 201 GB, far beyond 256 MB. The budget is huge, but the benefits are small: the total benefit is at most 200 x 1000 = 200,000. Define dp[v] as the minimum cost of a subset with total benefit exactly v. Initialize dp[0] = 0 and all other entries to infinity. For each project (c, b), iterate v downward from current maximum benefit to b and set dp[v] = min(dp[v], dp[v-b] + c) when dp[v-b] is finite. The answer is the largest v with dp[v] <= B. There are 200 x 200,000 = 40 million transitions, well under the one-second guideline, and a one-dimensional array of 200,001 64-bit integers is about 1.6 MB. This is the standard value-indexed knapsack and fits the machine comfortably.
2. Give a counterexample showing that the benefit/cost greedy rule can be suboptimal for this 0/1 instance.
Read the worked answer
Take budget B = 20, project X with cost 10 and benefit 60, and project Y with cost 20 and benefit 100. The ratios are 6 for X and 5 for Y. Greedy sorts X first, takes it, has 10 units left, cannot afford Y, and obtains benefit 60. The optimal subset is {Y} with benefit 100. The greedy exchange argument fails because taking the higher-ratio item can consume capacity that a single slightly less efficient item would have used completely. This counterexample scales directly to the allowed ranges: costs 10 and 20, benefits 60 and 100, budget 20. Therefore the colleague's greedy method is not acceptable when an exact answer is required; it is only a heuristic. The value-indexed DP from the previous part remains exact.
3. For the variant n = 40, B = 10^9, bi up to 10^9, outline an exact algorithm that fits the machine.
Read the worked answer
Use meet-in-the-middle. Split the 40 projects into two halves of 20. Enumerate all 2^20 subsets of each half, keeping (cost, benefit) for subsets with cost at most B. For the right half, sort by cost and build a prefix maximum of benefit so that for any cost limit we can query the best benefit achievable within that limit by binary search. Then enumerate each left subset (costL, benefitL), query the right half for the best benefit with cost at most B - costL, and maximize benefitL + rightBenefit. Each half has about 1,048,576 subsets; storing pairs of 64-bit integers is about 16 MB per half, and the sort and queries take on the order of 2^20 log 2^20 operations, roughly 20 million comparisons. This is exact and fits 256 MB. It avoids both the 10^9 budget dimension and the 10^9 benefit dimension.