Pszeudokód vagy algoritmus a legegyedibb értékkel rendelkező „n” halmazok megtalálására?

Ha a halmazok összszáma = N nem túl nagy: a nyers erő megközelítés a következő lenne: vegye figyelembe az (N válasszon n) lehetséges halmazkombinációt, és értékelje ki az általuk alkotott egyedi egész számok számát a "duplikátumok egyesítésével és eltávolításával vektorban, majd ellenőrizze a méretet", amíg minden kiértékelés után a maximumot nem kapja. ebből kiindulva egyre hatékonyabb algoritmusokat készíthet dinamikus programozással vagy sok (N válasszon n) kiiktatásával, például miután talált néhány MAX=K értéket, akkor ha ebben az n halmazban az int-ek teljes száma kisebb, mint K nem értékeli...stb ez egy durva vázlat az induláshoz

Megcímkézted a C++-t. Ha jól értem, akkor az alábbiak azt teszik, amit leírtál. Mivel az std::set amúgy is egyedi értékeket tárol, a C++ kódmegoldás egyszerűvé válik.

#include <vector>
#include <set>
#include <algorithm>
#include <iostream>

typedef std::set<int> IntSet;
typedef std::vector<IntSet> IntSetV;

// sort the sets in ascending order, by size
bool SortBySetSize(const IntSet& s1, const IntSet& s2)
{ return s1.size() > s2.size(); }

void OutputResults(const IntSet& s)
{  std::cout << "There are " << s.size() << " unique integers in this set" << std::endl; }

void InputData(IntSet& s)
{
   // routine to input data into s
}

using namespace std;
int main()
{
   size_t nSets;
   cout << "Enter number of sets: ";
   cin >> nSets;

   IntSetV VSets(nSets);
   //...  input to fill in the sets in the vector
   for_each(VSets.begin(), VSets.end(), InputData);

   // sort the sets by size
   std::sort(VSets.begin(), VSets.end(), SortBySetSize);

   // VSets now contains the N largest set of unique integers.
   for_each(VSets.begin(), VSets.end(), OutputResults);
}

Ha emlékeznie kell az eredetileg bevitt értékekre, tárolja

std::pair<std::vector<int>, IntSet> PairSet;
std::vector<PairSet> IntSetV;

A pár első értéke az eredeti vektor, a második az a halmaz, amely a vektorban szereplő számokat reprezentálja. Ezután az általános kódmegoldás használható a szükséges változtatásokkal.

Ez az NP-nehéz maximális lefedettségi probléma. A mohó algoritmus (az unió növelése a legtöbb új elemet tartalmazó halmazzal) olyan megoldást ér el, amely az optimum 1-1/e (~ 63%) tényezőjén belül van. Bár a maximális lefedettség NP-nehéz, az egészszámú programozás gyakran talál optimális megoldást a „természetes” példányokra (szemben az intelligensen megtervezett NP-keménységcsökkentéssel). A fő kihívás egy megoldó integrálása lenne; konkrétan a megoldó megvalósítja az összes releváns algoritmust. A legegyszerűbb készítmény a maximális fedés érdekében ez.

maximize sum_{elements e} x_e
subject to
for all elements e, x_e - sum_{input sets S such that e in S} y_S <= 0
sum_{input sets S} y_S <= n
for all elements e, 0 <= x_e <= 1
for all input sets S, y_S in {0, 1}

A x_e változó jelentése az, hogy a x_e megjelenik-e az unióban. A y_S jelentése 1, ha S szerepel az unióban, és 0 egyébként.