选择选择的最大数目 [英] Selecting Maximum Number of Choice

问题描述

我们正在指定N水果和M的选择，以选择那些fruits.M线有一定的整数，第一个是K和各M行如下ķ整数第一值（即K）表示的果实指数​​为后在这样的选择中选择。 我需要找出可以选择的选项的最大数量。

We are given N fruits and M choices to select those fruits.M lines have some integers and the first one is K and each M lines follows K integers after the first value (ie. K) denoting the indices of fruit to be selected in that choice. I need to find out the maximal number of choices that can be selected.

注： - 只有一个特定的索引水果

Note :- There is only one fruit at a particular index.

采样输入： -

4 3

2 1 2

2 2 3

2 3 4

输出： -

2

我们可以选择第一和第三选择。

As we can select 1st and 3rd choice.

的算法，我应该用它来解决这个问题？

Which Algorithm should I use to solve this question ?

推荐答案

这是集装箱问题，的经典NP完全问题之一。没有有效的解决方案，但你可以尝试一个回溯算法（慢但精确的）或贪婪的近似（快，但不理想）。

This is the set packing problem, one of the classic NP-complete problems. There is no efficient solution, but you can try a backtracking algorithm (slow but exact) or a greedy approximation (fast but suboptimal).

这篇关于选择选择的最大数目的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！