算法 - 要获得 "impressive"数字集，您必须进行多少更改

Question

问题

一组令人印象深刻的数字是一组，其中每个数字都包含 k 个 k 个数字。

例如 (5, 5, 5, 5, 5), (2, 2, 3, 3, 3, 1) 和 (2 , 2, 1) 是令人印象深刻的集。

(3, 3, 2) 不是一个令人印象深刻的集合，因为有两个3(应该是三个)和一个2(应该是两个)。

有一个 n 整数列表 a_i 使得 (1 ≤ n ≤ 2000, 1 ≤ a_i ≤ 2000) .

找到获得令人印象深刻集的最小更改量。您一次可以更改一个号码。顺序无关紧要。最后一组是什么并不重要。

例子

• 输入:(3, 4, 3, 2, 1) -> (3, 3, 3, 2, 1) -> (3, 3, 3, 2, 2) = => 输出:2
• 输入:(5, 5, 5, 5, 5, 5, 5) -> (5, 5, 5, 5, 5, 5, 2) -> (5, 5 , 5, 5, 5, 2, 2) ==> 输出:2
• 输入:(2, 2, 3, 3) -> (2, 3, 3, 3) -> (1, 3, 3, 3) ==> 输出: 2

输入/输出

函数的输入是一个列表。输出是 int，表示最小更改量。

旁注

该程序应该用 C++ 编写，内存限制为 64MB。当然，我不是在寻求解决方案，而是在寻求算法方面的提示。

Answer 1

基本上等于subset sum problem .首先建表，然后提取子集总和中成本最小的解之一。

例如，对于 1,2,3,4,5,5，我们在数组中有 6 个位置和五个数字 1,2,3, 4,5。从这些数字中，我们需要找到总和为 6 的子集。然后选择构建令人印象深刻的集合所需的更改最少的一个。

算法的复杂度是O(n^2)。

#include <iostream>
#include <array>
#include <algorithm>
#include <cassert>
#include <numeric>
#include <vector>

const short N = 2000;
short dp[N + 1][N];
const short NO = std::numeric_limits<short>::max();

class Impressive {
    short sum;
    std::array<short, N + 1> count = { { 0 } };
    const std::vector<short>& input;

    void SubsetsumDp()
    {
        for (short i = 1; i <= N; ++i) {
            for (short j = 1; j <= sum; ++j) {
                short to_replace = i - count[i];
                if (i == j) dp[i][j] = to_replace;
                if (i > 0) {
                    if (dp[i - 1][j] != NO) {
                        dp[i][j] = std::min(dp[i][j], dp[i-1][j]);
                    }
                    if (j - i > 0) {
                        if (dp[i-1][j-i] != NO)
                        dp[i][j] = std::min(dp[i][j], (short)(dp[i - 1][j - i] + to_replace));
                    }
                }
            }
        }
    }

public:
    Impressive(const std::vector<short>& v) : input(v)
    {
        for (int i = 0; i <= N + 1; ++i) {
            for (int j = 0; j <= N; ++j) {
                dp[i][j] = NO;
            }
        }
    }

    short Solve()
    {
        for (auto i : input) if (count[i] < i) ++count[i];
        sum = (short)input.size();
        SubsetsumDp();
        return dp[input.size()][sum];
    }
};

void Test(const std::vector<short>& v)
{
    std::copy(v.cbegin(), v.cend(), std::ostream_iterator<short>(std::cout, " "));
    std::cout << std::endl << Impressive(v).Solve() << std::endl << std::endl;
}

int main()
{
    std::vector<short> input(2000);
    std::iota(input.begin(), input.end(), 1);
    Test(input);

    Test({ 1, 1, 2, 3, 4, 5 });
    Test({ 1, 2, 3, 4, 5 });
    Test({ 5 });
    Test({ 3, 2, 1, 1, 1 });
    Test({ 4, 5, 5, 8, 8, 8, 8, 8 });
    Test({ 4, 4, 5, 5, 9, 9, 9, 9, 9 });

    return 0;
}

...
1938

1 1 2 3 4 5
3

1 2 3 4 5
3

5
1

3 2 1 1 1
3

4 5 5 8 8 8 8 8
3

4 4 5 5 9 9 9 9 9
4