1
$\begingroup$

I understand the basics of the 0-1 problem and its solution.

I have a variant of it that I'm trying to solve in a decent way and I'm struggling on it, mostly because of the 0-weighted items. These are the rules:

  • I have k finite sets of items. Each item has a weight and a value.
  • I must take exactly one item from each set.
  • Zero-weighted items are allowed. But since you are not allowed to take more than one item from each set, it's not always convenient to take them.
  • Weights in each set are the first natural numbers {0, 1, 2, 3...i}.
  • In each set, values are non-decreasing when the weight increases.
  • I want to determine which items maximize the total value for a certain total weigth.

example:

Set Weight 0 Weight 1 Weight 2 Weight 3 Weight 4 Weight 5
A 3 6 6 9 15 26
B 0 6 8 - - -
C 1 1 10 15 16 -

The notation "B3" means "Select the object from set B that weights 3".

The solutions for a maximum total weight = n are:

  • n=0 -> [A0; B0; C0] => Total Value = 4
  • n=1 -> [A0; B1; C0] => Total Value = 10
  • n=2 -> [A0; B0; C2] OR [A1;B1;C0] => Total Value = 13
  • n=3 -> [A0; B1; C2] => Total Value = 19
  • n=4 -> [A0; B1; C3] => Total Value = 24
  • n=5 -> [A1; B1; C3] OR [A5;B0;C0] => Total Value = 27
  • n=6 -> [A5; B1; C0] => Total Value = 33
  • n=7 -> [A5; B0; C2] => Total Value = 36
  • n=8 -> [A5; B1; C2] => Total Value = 42
  • n=9 -> [A5; B1; C3] => Total Value = 47
  • n=10-> [A5; B2; C3] => Total Value = 49
  • n=11-> [A5; B2; C4] => Total Value = 50
  • n>=12 it's the same as n=11.

Do you have some clue for implementing a decent algorithm to find the best combination of items to solve this problem with a generic collection of such set? Thanks!

Improve this question
$\endgroup$
2
  • $\begingroup$ I suspect some aspect of the problem statement is missing. Do you perhaps have a max total weight as an input, and any valid solution must ensure that the sum of weights of the selected items is at most that max? What are all the inputs to the algorithm? $\endgroup$
    – D.W. ♦
    Commented Jun 17, 2022 at 0:25
  • $\begingroup$ Yes, that's right... I forgot to specify that. I edit the post! $\endgroup$
    – boulayo
    Commented Jun 17, 2022 at 7:26

2 Answers 2

Reset to default
0
$\begingroup$

If weights aren't too large, use the standard pseudo-polynomial-time algorithm (using dynamic programming) for the knapsack problem. It is easy to adjust to this setting. See https://en.wikipedia.org/wiki/Knapsack_problem#0-1_knapsack_problem.

If weights can be large, use integer linear programming, and apply an off-the-shelf ILP solver.

Improve this answer
$\endgroup$
0
$\begingroup$

If I have realized the problem, I think this problem is more similar to matching problem than knapsack problem.

In other words, you can introduce a bipartite graph with two sets $S$ of objects (A, B, C, ...) and $T$ of weights ($0, 1, 2 ,...$) and a weighted arc between each object i to each weight j; e.g. weight of the edge $v_{A5}$ is equal to $26$ in your example.

enter image description here

Then, to produce a solution with maximum weight, you can not select more than one item from each weight (Otherwise, we don't need to solve any problem and the solution is to select the largest weights from each object). Therefore, you can solve the maximum matching on the proposed graph (if you want to select at most one item from each object and at most one item from each weight).

But, if you can select more than one item from each weight then you should add another constraint to the problem; e.g. Weighted sum of the selected objects is less than $k$. In this case, introduce decision variables $x_{ij}:=\{1: $ if we select object from set i that weights j , $0:$ Otherwise $\}$ and solve the following ILP model:

$min\ \sum_{i,j}w_{ij}x_{ij}\ $

  1. $\sum_{j}x_{ij} = 1 \ \ i\in S$
  2. $\sum_{i,j}w_{ij}x_{ij} \le k$
  3. $x_{ij} \in \{0,1\}$
Improve this answer
$\endgroup$
7
  • $\begingroup$ We introduced a bipartite matching where no two selected edges have a common endpoint and this concludes that we select exactly one item from each object (set of objects is smaller than set of weights) and at most one item from each weight. $\endgroup$
    – Majid Zohrehbandian
    Commented Jun 16, 2022 at 3:56
  • $\begingroup$ I completed my answer based on my realization about the problem (I had to edit it and I could not add it in a comment). $\endgroup$
    – Majid Zohrehbandian
    Commented Jun 16, 2022 at 12:48
  • $\begingroup$ I think I'm starting to appreciate the idea more, it is a clever way to ensure we get only one item per set. But I think there is a problem: using maximum matching in this way prevents us from taking two items from two different sets if they have the same weight. So this doesn't necessarily give the optimal solution. For example, suppose the weight-0 item in set A has the highest value of any item in set A, and the weight-0 item in set B has the highest value of any item in set B. Then the optimal solution is to pick those two weight-0 items, but matching will never choose that solution. $\endgroup$
    – D.W. ♦
    Commented Jun 16, 2022 at 17:48
  • $\begingroup$ Yes. You right and as I said, if we can select more than one item from each weight then we need another constraint for the problem. Hence, we can not solve the maximum matching and we should solve an ILP model. $\endgroup$
    – Majid Zohrehbandian
    Commented Jun 16, 2022 at 19:59
  • $\begingroup$ Perhaps we can have one node on the right per item, rather than per weight? $\endgroup$
    – D.W. ♦
    Commented Jun 17, 2022 at 0:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.