信息学奥赛一本通 1273:【例9.17】货币系统

信息学奥赛一本通 1273:【例9.17】货币系统题目链接 ybt 1273 例 9 17 货币系统 注 题目中 0 lt n 100 0

大家好,我是讯享网,很高兴认识大家。

【题目链接】

ybt 1273:【例9.17】货币系统
注:题目中 0 < n ≤ 100 0<n\le 100 0<n≤100, 0 < m ≤ 10000 0<m\le 10000 0<m≤10000
结果要用long long表示

【题目考点】

1. 动态规划:完全背包问题

【解题思路】

1. 状态定义
  • 集合:选择货币的方案
  • 限制:选择哪些种类面值的货币,凑多少钱
  • 属性:货币面值加和
  • 条件:等于m
  • 统计量:方案数

状态定义:dp[i][j]:在前i种货币中选择货币凑j元钱的方案数。
初始状态:前i种货币中选择货币凑0元的方案数为1,不选任何货币也算一种方案。dp[i][0] = 1


讯享网

2. 状态转移方程

记第i种货币的面值为a[i]
集合:在前i种货币中选择货币凑j元钱的方案。
分割集合:是否选择第i种面值的货币

  • 子集1:如果不选择第i种面值的货币,那么在前i种货币中选择货币凑j元的方案数,为在前i-1种货币中选择货币凑j元的方案数,为dp[i-1][j]
  • 子集2:在要凑的钱数j大于等于第i种货币的面值a[i]的情况下,如果选择第i种货币,下一次还可以选择第i种货币。那么还需要在前i种货币中选择货币凑j-a[i]元。在前i种货币中选择货币凑j元的方案数,为在前j种货币中选择货币凑j-a[i]元的方案数,为dp[i][j-a[i]]
  • 以上两种情况得到的方案数加和,即为在前i种货币中选择货币凑j元的方案数。dp[i][j] = dp[i-1][j] + dp[i][j-a[i]]
    原解法时间复杂度: O ( m ∗ n ) O(m*n) O(m∗n),空间复杂度: O ( m ∗ n ) O(m*n) O(m∗n)。
    可以对该问题使用滚动数组优化,时间复杂度: O ( m ∗ n ) O(m*n) O(m∗n),空间复杂度 O ( n ) O(n) O(n)。

【题解代码】

解法1:基本解法,二维状态
#include<bits/stdc++.h> using namespace std; #define N 105 #define M 10005 long long m, n, dp[N][M], a[N];//dp[i][j]:前i种货币凑j元的方案数  int main() { 
    cin >> n >> m; for(int i = 1; i <= n; ++i) cin >> a[i]; for(int i = 0; i <= n; ++i)//前i种货币中选择货币凑0元的方案数为1 dp[i][0] = 1; for(int i = 1; i <= n; ++i) for(int j = 0; j <= m; ++j) { 
    if(j >= a[i]) dp[i][j] = dp[i-1][j] + dp[i][j-a[i]]; else dp[i][j] = dp[i-1][j]; } cout << dp[n][m]; return 0; } 

讯享网
解法2:滚动数组优化,一维状态
讯享网#include<bits/stdc++.h> using namespace std; #define N 105 #define M 10005 long long m, n, dp[M], a[N];//dp[i][j]:前i种货币凑j元的方案数  int main() { 
    cin >> n >> m; for(int i = 1; i <= n; ++i) cin >> a[i]; dp[0] = 1; for(int i = 1; i <= n; ++i) for(int j = a[i]; j <= m; ++j) dp[j] = dp[j] + dp[j-a[i]]; cout << dp[m]; return 0; } 
小讯
上一篇 2025-03-12 22:39
下一篇 2025-04-08 23:14

相关推荐

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容,请联系我们,一经查实,本站将立刻删除。
如需转载请保留出处:https://51itzy.com/kjqy/115200.html