0

I have the Coin Changing problem except with a twist: instead of finding solutions from infinite coins to equal a single sum, find a list of solutions from a finite set of coins to be less-than a collection of sums.

(A great link to the classic problem is here)

(This is also similar to subset-sum problem, except with a set of targets instead of just one - link here)

A similar, but different and seemingly more difficult problem to code:

Given -

  • A list of possible numeric values that all must be used [1, 9, 4, 1, 3, 2]
  • A list of groups with a maximum total that can be achieved [(GroupA,17), (GroupB,1), (GroupC,5)]

Goal - Assign each numeric value from the list to a Group, so that all items are used with the following constraint: the total sum of the values for each group must not exceed the assigned maximum.

For example, this example might find 3 solutions:

[[GroupA,[9,4,1,3]], [GroupB, [1]], [GroupC, [2]],
[GroupA,[9,4,1,2]], [GroupB, [1]], [GroupC, [3]],
[GroupA,[9,2,1,3]], [GroupB, [1]], [GroupC, [4]]]
Josh
  • 1,493
  • 1
  • 13
  • 24

1 Answers1

1

This is called the multiple knapsack problem. You have n items with weights w[i], and m knapsacks with capacities c[i], and you need to assign the items to the knapsacks so that none exceeds its capacity.

Wikipedia provides the integer programming formulation of the problem, and that's the approach I'd take to solving practical examples -- by using an IP solver.

For completeness, the IP formulation is:

maximize sum(x[i,j] * w[j], i=1..m, j=1..n)
such that:
sum(x[i,j], i=1..m) <= 1 (for all j=1..n)
sum(x[i,j] * w[j], j=1..n) < c[i]  (for all i=1..m)
x[i][j] = 0 or 1 (for all i=1..m, j=1..n)

That is, you're maximizing the total weight of things in the knapsacks, such that no item is assigned to more than one knapsack, no knapsack exceeds its capacity, and items are discrete (they can't be partially assigned to a knapsack). This is phrased as an optimization problem -- but of course, you can look at the best solution and see if it assigns all the items.

Paul Hankin
  • 54,811
  • 11
  • 92
  • 118