Algo to find optimum solution from a given dataset [closed]

Question

Closed. This question needs details or clarity. It is not currently accepting answers.

---

Want to improve this question? Add details and clarify the problem by editing this post.

Closed 8 years ago.

Improve this question

Suppose i have a given data set.

 4 → a b c
 5 → l b d
 6 → e b c
42 → l b c

Here data items are in group such that their combined value is given in first column. To be more accurate, the items are clubbed in different ways.

The input to the algorithm should be the items. Output should be the best possible combination through which we obtain all item set with minimum cost.

Example.
To get b, c, l, and e values, we need to take the row with a key of 5 and the row with the key of 6. Returning the sum of 5 and 6.

programm b c l e
    output: 11 = 5+6

Here, we must return 4+5 = 9. Although the row with the key of 42 also matches the criteria, 9 < 42.

programm l b c
    output: 9 = 4+5

programm e b c
    output: 6

Answer 1

Clearly, you can remove elements from the sets that are not part of the query set. Then, what remains is the weighted Set Cover problem. It is NP-hard, thus difficult so solve optimally. Possibly the greedy heuristic is sufficient; if you really need an optimal solution, I'd try first to investigate whether your input instances have any properties that might be exploited, or otherwise use an ILP solver.