hard20 pts · first answer countsdynamic-programmingknapsack

Knapsack with a capacity of a billion

There are 100 items, the capacity is 10^9 and each value is at most 1,000. The usual O(n × W) DP is too big. What works instead?

A.Greedy by value-to-weight ratio, then fill upB.Sort by weight and take items until the bag is fullC.Divide every weight by 10^6, round, then run DPD.DP over value: dp[v] = least weight for value v

Discussion 0

Join free to post in the discussion.

Knapsack with a capacity of a billion

Discussion 0

Related questions