1
$\begingroup$

A sub-set sum problem is described that giving a set of integers $S$ and a constant $C$, find a subset $s$ of $S$ so that the sum of integers in $s$ is maximum but not greater than $C$. $$maximize\sum_{i=0}^{|S|} v_ix_i \ \ \ subject\ to \sum_{i=0}^{|S|} v_ix_i \le C$$ where $v_i \in S$ and $x_i\in \{0,1\}$

We have an extra problem here. Give two sets of numbers $A = \{a_1, a_2, a_3, a_4, a_5\}$ and $K = \{k_1, k_2, k_3, k_4\}$ and a number of lists in order as below: $$ \begin{align*} L_1 &= \{a_1, a_4\} \\ L_2 &= \{a_1, a_2, a_3, a_4\} \\ L_3 &= \{a_3, a_4, a_5\} \\ L_4 &= \{a_5\} \end{align*} $$ Assign $S_i$ is the expected result for sub-set sum problem of $L_i$. Find a subset of $A$ so that if an element of this subset appears both $S_i$ and $L_{i+1}$, it must also be in $S_{i+1}$

For each list, find a subset sum with a respective constraint in $K$ ($L_1 \leftrightarrow k_1$, $L_2 \leftrightarrow k_2$, and so on). The procedure is described as following:

  • First, we can see that $L_1$ contains the subsets like $\{a_1\}, \{a_4\}$ and $\{a_1, a_4\}$, we then assume a subset $S_1=\{a_1,a_4\}$, with $a_1$ and $a_4$ sum up to $k_1$, is the expected result for $L_1$
  • Next, we have to solve the subset sum problem with $L_2$ by finding a subset $S_2$ with a restriction (because $a_1,a_4$ also appear in $L_2$, so $S_2$ must contain $a_1,a_4$). Therefore all possible states of $S_2$ are $\{a_1, a_4, a_3\}, \{a_1, a_4, a_2\}, \{a_1, a_4, a_2, a_3\}$. Assume that $S_2 = \{a_1, a_4, a_3\}$ is the expected subset for $L_2$
  • We then continue playing with $L_3$. Similarly, we can see $a_3, a_4$ also appear in $L_3$, thus $S_3$ must contain $a_3, a_4$, i.e., $S_3=\{a_1,a_4,a_3\}$.
  • Finally, the subset $B = \{a_1, a_4, a_3\}$ is final result what I expect.

For example $A = \{1, 2, 3, 4, 5\}$ and $K = \{7, 8, 9, 10\}$
$L_1 = \{1, 4\}, k_1 = 7$, due to $1 < 4 < (1+4) < 7$ so $S_1=\{1, 4\}$
$L_2 = \{1, 2, 3, 4\}, k_2 = 8$, due to $(1+4+2) < (1+4+3) <= 8 < (1+4+2+3)$ so $S_2 = \{1, 4, 3\}$ $L_3 = \{3, 4, 5\}, k_3 = 9$, due to $(4+3) < 9 < (4+3+5)$ then $S_3$ is same with $S_2$
$L_4 = \{5\}, k_4 = 10$, due to 5 is not in $S_3$ so we do not consider it, therefore $S_4$ is empty
The final result is $B = S_3 = \{1, 4, 3\}$

Currently, I can solve this problem with the brute-force algorithm. However, I'm finding any other faster ways. Does anyone have any suggestion for me?

$\endgroup$

closed as unclear what you're asking by Yuval Filmus, Evil, Gilles Dec 16 '18 at 19:37

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • 2
    $\begingroup$ Please credit the original source of the problem. $\endgroup$ – Apass.Jack Dec 16 '18 at 10:32
  • $\begingroup$ I don't understand which source I have to credit, this is my own problem. $\endgroup$ – hdng Dec 16 '18 at 13:49
  • $\begingroup$ Could you please share a bit of background how you come up with the problem? $\endgroup$ – Apass.Jack Dec 16 '18 at 14:03
  • $\begingroup$ This problem I came up with by expanding the special case of knapsack problem. $\endgroup$ – hdng Dec 16 '18 at 15:03
  • 1
    $\begingroup$ The problem is still extremely hard to understand, since you're not explaining it. $\endgroup$ – Yuval Filmus Dec 16 '18 at 18:56

Browse other questions tagged or ask your own question.