【AcWing】蓝桥杯集训每日一题Day21|背包问题|完全背包|DP|1371.货币系统(C++)

1371.货币系统
1371. 货币系统 - AcWing题库
难度:简单
时/空限制:1s / 64MB
总通过数:7096
总尝试数:12581
来源:

usaco training 2.3
算法标签

DP背包问题

题目内容

给定 V 种货币(单位:元),每种货币使用的次数不限。
不同种类的货币,面值可能是相同的。
现在,要你用这 V 种货币凑出 N 元钱,请问共有多少种不同的凑法。

输入格式

第一行包含两个整数 V 和 N。
接下来的若干行,将一共输入 V 个整数,每个整数表示一种货币的面值。

输出格式

输出一个整数,表示所求总方案数。

数据范围

1≤V≤25,
1≤N≤10000
答案保证在long long范围内。

输入样例:
3 10
1 2 5
输出样例:
10
题目解析

V种货币,每种货币的使用次数是不限的
不同的货币,面值可能是相同的也可能是不同的
要用V种货币凑出N元钱,问有多少种不同的凑法

输入若干行,总共输入V个数,不一定每行一个数,也不一定只有一行

最多有25种货币
总钱数最大是10000

非常经典的完全背包问题

把总钱数N看成背包容量
把每种货币看成是一个物品
每种物品可以用无限个

如果想装满背包的话,一共有多少种不同的方案

时间复杂度是N*V,25万

如何分析完全背包问题

从集合角度来分析

  1. 状态表示
    背包问题可以用一维来写,分析的时候最好用二维来分析
    f[i][j]
    i表示物品,j表示当前的背包容量
  • 当前状态表现的是哪个集合
    表示只用前i种货币,且总钱数是j的所有方案的集合
  • 存的是集合的哪个属性
    问的是方案数,所以属性就是集合当中的元素数量

只要把每一个状态都求出来,答案就是f[V][N]

  1. 状态计算
    集合的划分
    求这个集合的元素数量的话,一般是先将这个集合分成若干个子集,分别求每一个子集的元素数,再相加,就可以了

划分的时候一般是找最后一个不同点,也就是第i种货币用的数量
用第i种货币用的数量将集合分成若干类

  • 第一类是第i种货币用0个
  • 第二类是用1个
  • 第三类是用2个
  • 以此类推
    这种划分方案是不重不漏的
    每一种方案可以依据第i种货币的数量一定属于且仅属于某一个子集
    因此要求整个方案的方案数的话,只要分别求每个子集的方案数,再相加就可以了

如何求每一个子集的方案数

  • 先看一下第一个子集的方案数,从具体含义来看怎么求
    从1到i中选,且总金额是j的所有方案的集合,并且第i种货币选0个,等价于从1~i-1中选,总价值是j
    根据状态表示,它恰好就是f[i-1][j]

  • 第二个子集的方案数
    从1到i中选,总钱数是j,并且第i种货币用了1张,的所有方案的集合
    前面随便选,最后一个都是只包含1个第i种货币
    变化的部分就是前面,方案数就取决于前面可以变化出多少种

前面可以变化出多少种,要看前面变化的含义是什么
用1~i-1,凑出来 j − v i j - v_{i} jvi,的所有方案的集合
每一个前面的集合里面的方案加上一张 v i v_{i} vi,就可以构成这个子集的一个方案

根据状态的表示,恰好就是f[i-1][j - v]

  • 同理下一个子集的方案数就是f[i-1][j - 2 * v]
  • 以此类推

最终,
f[i][j] = f[i-1][j] + f[i - 1][j - v] + f[i - 1][j - 2 * v]...

状态数量是货币数量乘总金额25万
每个货币最多会用1万次
整个的时间复杂度 2.5 ∗ 1 0 9 2.5*10^9 2.5109

需要优化
通过公式变形,给这个式子做化简

用同样的方式把f[i][j - v]展开,相当于换元法,用j-v换掉v
f [ i ] [ j ] = f [ i − 1 ] [ j ] + f [ i − 1 ] [ j − v ] + f [ i − 1 ] [ j − 2 v ] … f [ i ] [ j − v ] = f [ i − 1 ] [ j − v ] + f [ i − 1 ] [ j − 2 v ] + f [ i − 1 ] [ j − 3 v ] … \begin{array}{} f[i][j] = f[i-1][j] + f[i - 1][j - v] + f[i - 1][j - 2v]\dots \\ f[i][j-v]=f[i-1][j-v]+f[i-1][j-2v]+f[i-1][j-3v]\dots \end{array} f[i][j]=f[i1][j]+f[i1][jv]+f[i1][j2v]f[i][jv]=f[i1][jv]+f[i1][j2v]+f[i1][j3v]
对比一下两个式子的后半部分,发现完全一样
所以第一个式子的后半部分其实就是
f [ i ] [ j ] = f [ i − 1 ] [ j ] + f [ i ] [ j − v ] f[i][j] = f[i-1][j]+f[i][j-v] f[i][j]=f[i1][j]+f[i][jv]
这样计算每个状态的时候就不需要循环10000次了,时间复杂度变为25万,可以过了

代码

二维空间写法

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

using namespace std;

typedef long long LL;

//N表示货币数量,M表示背包容量
const int N = 30, M = 10010;

int n, m;
int v[N];   //v表示每一个货币的面值
LL f[N][M];  //f是状态数

int main()
{
	scanf("%d%d", &n, &m);
	//先读入每一种货币的面额
	for (int i = 1; i <= n; i ++) scanf("%d", &v[i]);

	//定义初始,一张货币也没有,也是一种方案
	f[0][0] = 1;
	//枚举一下所有的状态
	for (int i = 1; i <= n; i ++)
		for (int j = 0; j <= m; j ++)
		{
			//左边的状态一定存在
			f[i][j] = f[i - 1][j];
			//后面的状态不一定存在,当j小于v的时候不存在
			if (j >= v[i]) f[i][j] += f[i][j - v[i]];
		}
	printf("%lld\n", f[n][m]);

	return 0;
}

优化空间的写法

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

using namespace std;

typedef long long LL;

//N表示货币数量,M表示背包容量
const int N = 30, M = 10010;

int n, m;
int v[N];   //v表示每一个货币的面值
LL f[M];  //f是状态数

int main()
{
	scanf("%d%d", &n, &m);
	//先读入每一种货币的面额
	for (int i = 1; i <= n; i ++) scanf("%d", &v[i]);

	//定义初始,一张货币也没有,也是一种方案
	f[0] = 1;
	//枚举一下所有的状态
	for (int i = 1; i <= n; i ++)
		for (int j = 0; j <= m; j ++)
		{
			//左边的状态一定存在
			//右边的j还没有更新过,就是上层循环的f[i-1][j]
			//左边的j是第i层循环算的j,就是f[i][j]
			f[j] = f[j];
			//后面的状态不一定存在,当j小于v的时候不存在
			if (j >= v[i]) 
				//左边的j是当前算的j,就是f[i][j]
				//由于是从小到大枚举的j,在算j的时候,j-v[i]已经在当前第i层循环算过了,所以右边这样写的话,用的就是第i层循环的j-v[i]
				f[j] += f[j - v[i]];
		}
	printf("%lld\n", f[m]);

	return 0;
}

再优化

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

using namespace std;

typedef long long LL;

//N表示货币数量,M表示背包容量
const int N = 30, M = 10010;

int n, m;
int v[N];   //v表示每一个货币的面值
LL f[M];  //f是状态数

int main()
{
	scanf("%d%d", &n, &m);
	//先读入每一种货币的面额
	for (int i = 1; i <= n; i ++) scanf("%d", &v[i]);

	//定义初始,一张货币也没有,也是一种方案
	f[0] = 1;
	//枚举一下所有的状态
	for (int i = 1; i <= n; i ++)
		for (int j = 0; j <= m; j ++)
		{
			f[j] = f[j]; //这句话是恒等式,可以删掉
			if (j >= v[i])  
			//当j小于v[i]的时候,循环会直接跳过,可以让j直接从v[i]开始枚举
				f[j] += f[j - v[i]];
		}
	printf("%lld\n", f[m]);

	return 0;
}

变成

	for (int i = 1; i <= n; i ++)
		for (int j = v[i]; j <= m; j ++)
				f[j] += f[j - v[i]];

完全背包问题,直接改完是等价的
01背包问题改完不等价,需要倒过来循环

上一篇:同一个pdf在windows和linux中的页数不一样


下一篇:python统计分析——一般线性回归模型