AcWing 1371. 货币系统【完全背包求方案数】 c++详细题解

墨蓝 2021-07-24 14:31 292阅读 0赞

## 题目 ##

给定 V 种不同面值的货币（单位：元），每种货币使用的次数不限。

现在，要你用这 V 种货币凑出 N 元钱，请问共有多少种不同的凑法。

**输入格式**  
第一行包含两个整数 V 和 N。

接下来的若干行，将一共输出 V 个整数，每个整数表示一种货币的面值。

**输出格式**  
输出一个整数，表示所求总方案数。

**数据范围**

1≤V≤25,  
1≤N≤10000

**输入样例：**

3 10  
1 2 5

**输出样例：**

## 二维DP ##

### **闫氏DP分析法：** ###

--------------------

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTYyOTI4NQ_size_16_color_FFFFFF_t_70]

**状态表示：** `f[i][j]` 表示 从前`i`种货币中选，且总价值恰好为`j`的所有选法集合的方案数。

那么`f[n][m]`就表示表示 从前`n`种货币中选，且总价值恰好为`m`的所有选法集合的方案数，即为答案。

**集合划分：**

按照第`i`种货币可以选 `0`个,`1`个，`2`个，`3`个，，，，`k`个划分集合 `f[i][j]`。其中`k*w[i] <= j`,也就是说在背包能装下的情况下，枚举第`i`种货币可以选择几个。

**状态计算：**

`f[i][j] = f[i-1][j]+f[i-1][j-w[i]]+f[i-1][j-2*w[i]],,,,,,+f[i-1][j-k*w[i]]` .

**ac代码**

#include<iostream>
    #include<cstdio>
    
    using namespace std;
    const int N = 30,M = 1e4 +10;
    long long  f[N][M]; // 方案数很大使用long long 来存
    int w[N];
    int main()
    { 
        int n,m;
        cin>>n>>m;
        for(int i = 1; i <= n; i++) cin>>w[i];
        
        f[0][0] = 1; // 使用0种货币，凑0元钱,也是一种方案
        
        for(int i = 1; i <= n; i++)
          for(int j = 0; j <= m; j++)
          { 
              for(int k = 0; k*w[i] <= j; k++)
                f[i][j] += f[i-1][j-k*w[i]];
          }      
        cout<<f[n][m]<<endl;
        return 0;
    }

## 一维DP ##

--------------------

**考虑优化**

`v`代表第`i`件物品的体积

`f[i][j] = f[i-1][j] + f[i-1][j-v]+f[i-1][j-2v]+,,,,,+f[i-1][j-kv])`

`f[i][j-v] = f[i-1,[j-v]+f[i-1][j-2v]+,,,,,+f[i-1][j-kv])`  
**因此：**

`f[i][j] = f[i-1][j]+f[i][j-v])`

**图示：**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTYyOTI4NQ_size_16_color_FFFFFF_t_70 1]  
**去掉一维：**

**状态计算为：** `f[j] = f[j] + f[j-v]`

**ac代码**

#include<iostream>
    #include<cstdio>
    using namespace std;
    const int N = 1e4 + 10;
    long long f[N];
    int main()
    { 
        int m,n;
        cin>>n>>m;
        f[0] = 1;  //初始化 f[0][0] = 1 
        for(int i = 1; i <= n; i++)
        { 
            int v;
            cin>>v;
            for(int j = v; j <= m; j++)
              f[j] += f[j-v];   // 状态计算方程
        }
        cout<<f[m]<<endl;
        return 0;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTYyOTI4NQ_size_16_color_FFFFFF_t_70]: /images/20210724/7264659c43f749bd80ea869ce85b6d29.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTYyOTI4NQ_size_16_color_FFFFFF_t_70 1]: /images/20210724/d9c71962978f48648ddd6ef944402209.png