Knapsack algorithm with proper ratio constraint and weight constraint

Question

Problem: You're a juice maker looking for the best suppliers for your business. The suppliers are selling concentrates that have 3 ingredients: X:Y:Z in different proportions. Your juice needs to have these proportions as 1:1:1, otherwise it won't be tasty. The weight of the concentrate is the sum of its ingredients in lbs and all the suppliers are selling their concentrates for the same price, however your truck can only carry up to 400 pounds of concentrates. Find the best suppliers for your business: buy (find) as many pounds of concentrate as you can (but less than 400lbs), knowing that the ratio of ingredients other than 1:1:1 won't be acceptable.

Input: The first line tells you how many concentrates are sold on the market (less than 200) The next n lines are about the proportions of the X:Y:Z ingredients of concentrates (in pounds)

Output: First line should be the sum of weight of the ingredients of concentrates you'll be buying (smaller than 400 lbs) The second line should tell how many concentrates you've got to buy to get this amount keeping the proper proportions

Example:

in:
4 //how many concentrates are sold on the market
1 2 3 //first concentrate contains 1lb of X, 2lbs of Y, 3 lbs of Z
0 4 1
1 3 4
1 1 1
2 1 0

out: 
12 //4lbs of ingredient X + 4lbs Y + 4lbs Z
3 //we're buying three concentrates: the first one, fourth and fifth (1 2 3; 1 1 1; 2 1 0) so we're getting the biggest amount of it with 1:1:1 ratio of ingredients

My solution: My solution was a brute-force method that's very slow when there are a lot of suppliers as its complexity is 2^(n-2) - this algorithm would just create all possible combinations of the concentrates we could buy and it would check if their proportions are 1:1:1, if yes then it would compare them and find the one with the highest amount of total ingredients totaling less than 400lbs.

I'm looking for a dynamic-approach algorithm, however, I have no idea how to do it with the proper ratio constraint.

Answer 1

Here's a method that might allow us a lower operational complexity than user3386109's great idea. Conduct the sums enumeration separately for each member of the triple, and trace a match for (index,cardinality) for combinations across the three enumerations: for each member of the triples, x, y, and z in (x,y,z) iterate over a separate one dimensional array representing sums up to 133, indexing cardinality:

# for example, Xs enumeration only
for index, (x,y,z) in triples:
  for s in [133 - x ... 0]
    if sums_x[s].cardinalities.length > 0:
      for cardinality in sums_x[s].cardinalities:
        sums_x[s + x].by_index.add( (index,cardinality + 1) ) # this is a set of (index,cardinality) tuples
        sums_x[s + x].cardinalities["cardinality + 1"].push( index ) # hash cardinality to indexes

  sums_x[x].by_index.add( (index,1) )
  sums_x[x].cardinalities["1"].push( index )

Once we've iterated over the three one-dimensional arrays, one for each member of the triples, we can trace possible matches. These are made rare by the low probability of tracing a consistent match of (sum,cardinality,index) across all three enumerations.

For example:

(1 2 3),(0 4 1),(1 3 4),(1 1 1),(2 1 0)

index = 0
sums_x[1].by_index = {(0,1)} # (index,cardinality)
sums_x[1].cardinalities = {"1": [0]} # cardinality: indexes

index = 1
sums_x[0].by_index = {(1,1)} # (index,cardinality)
sums_x[0].cardinalities = {"0,1": [1]} # cardinality: indexes
sums_x[1].by_index = {(0,1), (1,2)}
sums_x[1].cardinalities = {"1": [0], "2": [1]}

...

index = 4
sums_x[4].by_index = {(4,3), (4,4)} # (index,cardinality)
sums_x[4].cardinalities = {"2": [3], "3": [4], "4": [4]} # cardinality: indexes

sums_y[4].by_index = {(1,1), (3,2), (4,2), (4,3)}
sums_y[4].cardinalities = {"1": [1], "2": [3,4], "3": [4]}

sums_z[4].by_index = {(1,2), (2,1), (3,2), (4,3), (4,2)}
sums_z[4].cardinalities = {"2": [1,3,4], "1": [2], "3": [4]}

As we can see, for the sum 4 in this example, there is only one match of (index,cardinality) across all three sum structures, (4,3), which we can then trace back using the associated values:

sums_z[4]: 4,3 
  => val 0 => lookup by z sum (4 - 0) and cardinality (3 - 1) 
  => sums_z[4].cardinalities[2] yields only one match across: index 3
  => lookup by z sum (4 - 1) and cardinality (2 - 1)
  => sums_z[3].cardinalities[1] yields a match across: index 0
  => possible solution, indexes [4,3,0]

Answer 2

400/3 = 133 which means that the answer can have no more than 133 lbs of any ingredient. So the DP array is array[134][134][134], where each entry in the array is the number-of-concentrates-to-buy to achieve that combination.

That array has about 2.4 million entries in it, and the array needs to be scanned once for each input (less than 200). So you're looking at about 500 million operations to fill in the array. That's reasonable on a modern computer.

After the array is filled, a simple scan finds the answer

for ( i = 133; i > 0; i-- )
    if ( array[i][i][i] > 0 )
        the answer is array[i][i][i]