算法提高课汇总

算法思路

题意理解

构成金额$x$

一个货币系统$(n, a)$能够表示一个非负金额$x$ :

$\;\;\;\;\;\;x = t_1\times a_1 + t2\times a_2 + \cdots + t_n\times a_n, 其中a_i\gt 0, t_i\ge 0$.

两个货币系统等价

如果货币系统$(n, a)$和$(m, b)$等价, 则说明两个货币系统表示的金额$x$的集合相等.
即对$\forall x$, 若$(n, a)$能够表示, 则$(m, b)$也能表示; 若$(n, a)$不能, $(m, b)$也不能.

简化货币系统

简化一个货币系统, 以输入为例$\lbrace 3, 19, 10, 6\rbrace$. 因为$6 = 3\times 2$, 所以$6$可以剔除,
同理$19 = 3\times 3 + 10\times 1$, 简化后的货币系统$\lbrace 3, 10\rbrace$.

解题关键

我们需要分析出题目的性质, 对于货币系统$(n, a)$和其简化后的货币系统$(m, b)$, 有如下性质:

1. $a_i$可被$b_1\sim b_n$构成, 因为$a_i$一定可被$(n, a)$构成. 反之亦然.

2. 化简后的$(m, b)$, $\forall b_i$, 不能被$(m, b)$中其他金额表示, 否则还能化简.

3. $b_i\in (m, a)$, 即$\exists j, b_i = a_j$.

   • 反证法: 设$(m, b)$中$\exists b_i\notin (n, a)$, 由性质1, $b_i$可被$(n,a)$构成, 再
     由性质1, 构成$b_i$的$a$可被$(m, b)$构成, 由性质2不能存在被$(m, b)$构成的$b_i$.

算法实现

经过上述分析, 简化过程即判断每个$a_i$:

• $a_i$可被$(n, a)$中其他金额构成, 则剔除$a_i$.

• 否则, 不能剔除$a_i$, 剔除后$a_i$这个金额就无法表示了, 与最开始的货币系统不等价.

也就是每个$a_i$只存在选/不选, 不存在决策空间.

我们可以对$(n, a)$金额从小到大排序($a_i\gt 0$, 大的$a$只能被小的构成), 判断$a_i$能否
被$a_1\sim a_{i-1}$的金额构成. 也就是问题转换为物品($a_i$)数量任意, 判断能否恰好构成$m$的问题,
可用完全背包求方案数的思路求解.

代码实现

完全背包求方案数代码:

#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 110, M = 25010;

int n, m;
int a[N];
int dp[M];

int main()
{
    int T;
    cin >> T;
    while( T -- )
    {
        cin >> n;
        for( int i = 0; i < n; i ++ )   cin >> a[i];

        sort(a, a + n);
        m = a[n - 1]; //需要构成的最大金额
        memset(dp, 0, sizeof dp);
        dp[0] = 1;

        int res = 0;
        for( int i = 0; i < n; i ++ )
        {
            if( !dp[a[i]] ) res ++; //dp[i - 1][ai] = 0, 说明之前的金额无法构成ai
            for( int j = a[i]; j <= m; j ++ )
                dp[j] += dp[j - a[i]]; //方案数
        }
        cout << res << endl;
    }
    return 0;
}

因为对于状态属性Count我们只需关注是否为0, 所以可以简单的把Count --> Exists.

#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 110, M = 25010;

int n, m;
int a[N];
bool dp[M];

int main()
{
    int T;
    cin >> T;
    while( T -- )
    {
        cin >> n;
        for( int i = 0; i < n; i ++ )   cin >> a[i];

        sort(a, a + n);
        m = a[n - 1]; //需要构成的最大金额
        memset(dp, 0, sizeof dp);
        dp[0] = true;

        int res = 0;
        for( int i = 0; i < n; i ++ )
        {
            if( !dp[a[i]] ) res ++; //dp[i - 1][ai] = 0, 说明之前的金额无法构成ai
            for( int j = a[i]; j <= m; j ++ )
                dp[j] |= dp[j - a[i]]; //方案数
        }
        cout << res << endl;
    }
    return 0;
}