C++实现1. 子集覆盖的贪心算法。已知一个有限集X和X的一组子集F，如果F中所有子集的并等于X，则称F覆盖X。请使用贪心方法在多项式时间内从F中选取一组覆盖X且子集数目尽可能少（不一定最少）的子集。

Question

2.着色的NP完全性。已知3-SAT是NP完全的，证明着色问题是NP完全的。（第二个题不会）

1.思路
创建一个集合X，存放所有的元素；
创建一个散列表 ，F的子集作为键，对应的元素作为值；
创建一个集合 ，用于存放已选择的子集；
遍历散列表，找到覆盖了最多未覆盖的城市的子集，将其加入到已选择子集集合 中；
将上一步选择的子集所覆盖的X中元素从城市集合X中移除，同时将从F中选中的子集从散列表中移除；
重复执行 4、5 步，直至X集合为空。
2.目的
写不下去了，求帮忙续写或改写两道题

#include<iostream>
int X[]{1,4,5,6,9,7,8,10,66};
//设F有五个f子集
int f1[]{ 1,5,9,10 };
int f2[]{ 4,5,66,8,9 };
int f3[]{ 6,7,10,8 };
int f4[]{ 1,8,66,7 };
int f5[]{ 4,6,8,10 };
int f6[]{ 1,7,9,8 };
int* F[]{f1,f2,f3,f4,f5,f6};
int* F2[6]{ nullptr };//储存以选择的f数组
int sX{ sizeof(X) / sizeof(int) };
int sF{ sizeof(F) / sizeof(int) };

using namespace std;
int* getMaxcover(int**& F) {
    int CNT(0);
    int cnt[sizeof(F) / sizeof(int)]{};//存储每个f和X重叠元素个数
    for (int i = 0; i < sF; i++)
    {//遍历F
        for (int j = 0; i < sX; i++)
        {//遍历X
            for (int k = 0; i < (sizeof(F[i]) / sizeof(int)); i++)
            {//遍历f
                if (F[i][k] == X[j])
                    CNT++;//记录总共的重叠次数
            }
            if (i == 0) 
            cnt[i] = CNT;//f1的
                
            if (i > 0)
            cnt[i] = CNT - cnt[i - 1];//f2~f6的
        }
    }
    int maxcover = cnt[0];
    for  (int i = 0; i < sF; i++)
    {
        if (cnt[i + 1] > cnt[i]) {
            maxcover = cnt[i + 1];
        }
    }//找到存贮最多重叠元素的f数组
    return F[maxcover];
}


int* myDelete(int* f) {
    int* storeIndex = new int;
    for (int i = 0; i < sizeof(f) / sizeof(int); i++)
    {//遍历f
        for (int j = 0; i < sX; i++)
        {
            if (X[j] == f[i])
                storeIndex[i] = j;//存储X中和f相同元素的下标
        }
        //删去相同元素
        for (size_t i = 0; i < sizeof(storeIndex) / sizeof(int); i++)
        {
            for (int i = 0; i < sX; i++) {
                if (X[i] == storeIndex[i]) {
                    for (int j = i; j < sX - 1; j++) {
                        X[j] = X[j + 1];
                    }
                }
            }
        }
        int* X_ = new int(sX - sizeof(storeIndex) / sizeof(int));//删除相同元素后新的X数组
        X_ = X;
        return X_;
    }
}

int** deleteFromX(int* f) {
        for (int i = 0; i < sF; i++)
        {
                if (F[i] == f) {
                    for (int j = i; j < sF - 1; j++) {
                        F[j] = F[j + 1];
                    }
                    F[sF - 1] = nullptr;
                }
        }
        int** F_ = F;
        return F_;
}//返回新的F集合

Answer 1

贪心算法可以用这个

https://blog.csdn.net/misayaaaaa/article/details/72789998