Knapsack

SRM 140 · 2003-03-26 · by Yarin

Class Name: Knapsack

Return Type: int[]

Method Name: whichObjects

Arg Types: (vector<int>, vector<int>, int)

Problem Statement

Given n objects, each object having a positive integer value and a positive integer weight, find a subset of these objects so the total value of the objects in the set is maximized while the total weight of the same objects is not greater than a given maximum total weight.

If there are several subsets yielding the same best total value, pick the subset among these with the lowest total weight. If there is still a tie, pick the subset with the fewest objects. If there's a tie again, pick the subset that comes first lexicographically. If A and B are two sorted (in ascending order) int[] containing the indexes of the objects in the subsets, then A is lexicographically before B if there exist some j so that A[i]=B[i] (0<=i<j) and A[j]<B[j]. For instance, {0,1,5,8,9} is lexicographically before {0,2,3,4,5}.

Create a class Knapsack which contains the method whichObjects which takes a int[] weight and a int[] value and returns a int[] containing the index of the objects (0-based) in the best possible subset according to the priorities above. The elements in the return value should be in increasing order. Element 0 in value and weight correspond to object 0, etc.

Constraints

weight will contain between 1 and 34 elements, inclusive.
value will contain between 1 and 34 elements, inclusive.
weight will contain the same number of elements as value.
Each element in weight will be between 1 and 2,000,000,000, inclusive.
Each element in value will be between 1 and 2,000,000,000, inclusive.
The sum of all elements in weight will be between 1 and 2,000,000,000, inclusive.
The sum of all elements in value will be between 1 and 2,000,000,000, inclusive.
maxWeight will be between 1 and 2,000,000,000, inclusive.

Examples

{415,528,744,555,526,530,274,154,769}
{428,200,627,470,891,167,974,101,770}
2205
Returns: { 0,  4,  6,  7,  8 }

The best objects to select are 0, 4, 6, 7 and 8. The total weight becomes 2138, and the value 2534.

{2,4,8,16,16,4,8,32,16,16,24,24,8,16,12}
{1,2,4,8,8,2,4,16,8,8,12,12,4,8,6}
100
Returns: { 1,  3,  7,  10,  11 }

The value of all objects are exactly half their weight, so obviously the maximum value is at most 50. There are several ways to get that value, for instance, {1,2,3,4,7,10}, {3,4,7,10,14} and {1,3,7,10,11}. The first of these contains more objects than the other two, so that one is not the answer. Of the other two, the latter is lexicographically smaller, so this one is preferred.

{1,2,1,2,1,2,2,4,2,4,1,1,1,1,2,2,4}
{8,4,4,2,8,4,4,4,4,8,1,4,2,1,1,4,1}
15
Returns: { 0,  1,  2,  4,  5,  6,  9,  11,  12 }

{10,15,20}
{20,25,30}
8
Returns: { }

All objects weight more than the maximum weight, so the method returns {}.

{51302,27983,71667,12089,19588,64031,
 97596,2003,5100,61584,27432,7419,50365,
 2582,12821,51090,34725,94152,29702,
 99239,64167,661,40163}
{61693,84646,83719,51302,88549,5379,
 92979,2577,79031,72574,21805,63706,
 55248,36660,68135,25281,57868,35613,
 96663,78418,84348,92573,72048}
684929
Returns: { 0,  1,  2,  3,  4,  6,  7,  8,  9,  10,  11,  12,  13,  14,  15,  16,  18,  20,  21,  22 }

Submissions are judged against all 58 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class Knapsack with a public method vector<int> whichObjects(vector<int> weight, vector<int> value, int maxWeight) · 58 test cases · 2 s / 256 MB per case