Acwing算法提高课-货币系统(1021 && 532)

动态规划 && 完全背包问题 -- 货币系统

模板题 -- 货币系统 (opens new window)

1.题目描述：

给你一个n种面值的货币系统，求组成面值为m的货币有多少种方案。

输入格式

第一行，包含两个整数n和m。

接下来n行，每行包含一个整数，表示一种货币的面值。

输出格式

共一行，包含一个整数，表示方案数。

数据范围

n≤15,m≤3000

2.思路：

• 递推方程

  经典的完全背包问题思考方式，状态转移方程 f[i][j] 表示，只考虑前 i 种面值，构成面值为 j 的货币的方案的集合，其中 f[i][j] = 方案数。

  则f[i][j] 可以按照第 i 种面值选取几张来进行分类，选取一张则为f[i - 1][j - a[i]] .....，易得状态转移方程为：

  f[i][j] = f[i - 1][j] + f[i - 1][j - a[i]] + ... + f[i - 1][j - x * a[i]] // 注意x的范围，x = j / a[i]
  
  

  由状态转移方程可知，每一层只用到上一层的状态，故可使用滚动进行空间压缩

• 状态初始化

对于DP问题，状态初始化也是很重要的一步。一般来说是对f[0][0] 或者 f[0] 进行状态初始化，即赋值。

对于本题来说，我们需要确保f[1][a[1]] = 1，则易得需要f[0][0] = 1 。更一般来说，考虑f[i][j] 当 j % a[i] == 0的情况，一定会有一种方案是只使用a[i]货币，即f[i - 1][0] 代表一种存在的方案，所以，我们需要把f[i][0] 均初始化为1，对于滚动数组即f[0] = 1 。

也可以从实际角度出发理解状态初始化，根据实际意义，前i个物品构成面值0的方案数恒为1.

3.代码(一维滚动数组)

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 3010;
long f[N]; // 状态转移 滚动数组
int a[N];
int main()
{
    int n,m;
    cin >> n >> m;
    for (int i = 1; i <= n; i ++ )
        cin >> a[i];
    
    f[0] = 1;
    for (int i = 1; i <= n; i ++ )
    {
        for(int j = m; j >= 0; j --)
        {
            int x = j / a[i];
            while(x)
            {
                f[j] += f[j - x * a[i]];
                x -= 1;
            }
        }
    }
    cout << f[m] << endl; 
    
}

变型题 货币系统 (opens new window)

1.题目描述

​ 过长省略，见连接

2.思路

​ 已知货币系统(n,a)，希望找到与(n,a)等价的货币系统(m,b)，且使得m最小。

​ 改题目经分析易得，如果数组a[n]中的一个数a[i]不可以被其他数所表示，则a[i] 一定比不可少，反之a[i] 可有可无，可以删掉。

​ 那么我们的任务就变成，找到所有可以被其他数表示的a[i] 删除掉所有 a[i] 之后，剩下的个数即为m的值。

​ 下面的问题就是遍历每一个数字，判断其能否被其他数字表示，这时我们需要确定遍历序列顺序。易知，每个数只能被比自己小的数表示，所以升序列即为我们需要遍历的序列。

• 状态转移方程

  f[i][j] 表示，只考虑前 i 个数，能否表示 j , f[i][j] 为 bool 类型变量。

  则状态转移方程为：

  f[i][j] = f[i - 1][j] || f[i - 1][j - a[i]] ||  ......  || f[i - 1][j - x * a[i]] // x =  j / a[i]
  

• 状态初始化为

  f[0][0] = true or f[0] = true

3.代码

// 二维状态
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 25010;
const int M = 110;
bool f[M][N];
int a[N];
int main()
{
    int t;
    cin >> t;
    while(t --)
    {
        // 状态方程初始化
        memset(f, 0, sizeof f);
        f[0][0] = true;
        int n;
        cin >> n;
        for(int i = 1; i <= n; i ++)
            cin >> a[i];
        sort(a + 1, a + n + 1);
        int m = a[n];
        for(int i = 1; i <= n; i ++)
        {
            for(int j = 0; j <= m; j ++)
            {
                f[i][j] = f[i - 1][j] || f[i][j];
                int x = j / a[i];
                while(x)
                {
                    f[i][j] = f[i][j] || f[i - 1][j - x * a[i]];
                    x --;
                }
            }
        }
        int ans = 0;

        for (int i = 1; i <= n; i ++ )
        {
            if(f[i - 1][a[i]]) 
            {
                ans ++;
            }
        }
        cout << n - ans << endl;
    }
}
// 一维状态
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 25010;
const int M = 110;
bool f[N];
int a[N];
int main()
{
    int t;
    cin >> t;
    while(t --)
    {
        // 状态方程初始化
        memset(f, 0, sizeof f);
        f[0] = true;
        int n;
        cin >> n;
        for(int i = 1; i <= n; i ++)
            cin >> a[i];
        sort(a + 1, a + n + 1);
        int m = a[n];
        int ans = 0;
        for(int i = 1; i <= n; i ++)
        {
            if(f[a[i]]) ans ++;
            for(int j = m; j >= 0; j --)
            {
                int x = j / a[i];
                while(x)
                {
                    f[j] = f[j] || f[j - x * a[i]];
                    x --;
                }
            }
        }
        cout << n - ans << endl;
    }
}

​ 本题一维代码和二维代码之间的转换易懂。笔者开始采用二维写法而不使用一维写法的原因是当你得到所有状态f[i][j] 后，对于a[i] 是否可以剔除，需要判断f[i - 1][a[i]] 是否为true ，是则直接剔除，反之保留。所以笔者认为需要保存全部状态，但是我们可以发现对于a[i] 我们只需要其上层状态f[i - 1][a[i]] 所以大可以在第一层循环中进行判断，从而直接采用一维状态滚动数组，见代码77行。