背包问题求方案数(二)

简介: AcWing算法提高课内容,本文讲解 动态规划

货币系统

题目要求

题目描述:

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

输入格式:

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

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

输出格式:

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

数据范围:

n≤15,m≤3000

输入样例:

3 10
1
2
5

输出样例:

10

思路分析

f[i]代表恰好用了 i元钱的时候的方案数,注意本题会爆 i n t,需要开longlong

代码

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 3010;
LL f[N];
int main()
{
    int n, m;
    cin >> n >> m;
    f[0] = 1;
    for (int i = 1; i <= n; i ++ )
    {
        int w;
        cin >> w;        
        for (int j = w; j <= m; j ++ )
            f[j] += f[j - w];
    }
    cout << f[m] << endl;
    return 0;
}

货币系统

题目要求

题目描述:

image.png

输入格式:

image.png

输出格式:

输出文件共有 T 行,对于每组数据,输出一行一个正整数,表示所有与 ( n , a )等价的货币系统 ( m , b )  中,最小的 m 。

数据范围:

1≤n≤100,

1≤a[i]≤25000,

1≤T≤20

输入样例:

2 
4 
3 19 10 6 
5 
11 29 13 19 17 

输出样例:

2
5

思路分析

image.png

代码

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 25010;
int w[N];
int f[N];
int main()
{
    int T;
    cin >> T;
    while (T -- )
    {
        int n;
        cin >> n;
        for (int i = 1; i <= n; i ++ ) cin >> w[i];
        sort(w + 1, w + n + 1);
        memset(f, 0, sizeof f);
        f[0] = 1;
        int m = w[n];
        int res = 0;
        for (int i = 1; i <= n; i ++ )
        {
            if (!f[w[i]]) res ++;
            for (int j = w[i]; j <= m; j ++ )
                f[j] += f[j - w[i]];
        }
        cout << res << endl;
    }
    return 0;
}





目录
相关文章
|
JSON 小程序 JavaScript
【微信小程序】-- 自定义组件 - 组件所在页面的生命周期 & 插槽(三十七)
【微信小程序】-- 自定义组件 - 组件所在页面的生命周期 & 插槽(三十七)
|
Android开发
autojs修改悬浮窗按钮点击事件
牙叔教程 简单易懂
2209 0
|
3月前
|
机器学习/深度学习 人工智能 编解码
AI视频生成技术全解析:从一段文字到一段视频AI是怎么做到的
AI视频生成是如何实现的?本文从技术原理角度解析AI视频从文本描述到动态视频的完整流程,包括扩散模型、时序建模等核心技术。
1048 0
|
4月前
|
SQL 关系型数据库 MySQL
MySQL版本升级最佳实践:从5.7到8.0再到8.4 LTS的兼容性审计与迁移策略
以一次真实升级事故开篇,覆盖MySQL 5.7→8.0→8.4升级路径、LTS与Innovation双轨线、兼容性审计、高危变更、升级路径对比与灰度切换策略
|
11月前
|
自然语言处理 搜索推荐 安全
2025数字人平台应用解析:各数字人定制场景化实践与技术特点
“来灵数字人”由苏州咖豆信息研发,聚焦数字人技术的实用化落地,推动其从形象展示向智能交互升级。平台具备系统协同、多模态交互、数据安全、行业知识嵌入与持续优化能力,已在零售、教育、金融等领域实现应用,提升服务效率与用户体验,助力企业数字化转型。
381 4
|
7月前
|
边缘计算 监控 Serverless
基于 Serverless 与云边协同的 Mobile Agent 架构:侠客工坊技术解析
本文介绍“侠客工坊”提出的云边协同Mobile Agent架构,以解决云原生时代移动端执行断层问题:通过Serverless事件驱动调度、端侧轻量Vision-SLM视觉推理、全链路多模态可观测性及内核级零侵入输入,实现高可用、可监控、合规的移动智能自动化。
604 0
|
8月前
|
SQL BI 数据库
企业智能问数平台的真正分水岭:本体语义层与预置指标层到底差在哪?
企业智能问数平台成败关键不在大模型或界面,而在于底层数据治理逻辑:是构建“预置指标层”(稳态可控、适合成熟BI体系),还是打造“本体语义层”(弹性扩展、支撑跨域复杂分析)。选型需权衡建设成本、维护负担与长期演进能力。
|
8月前
|
算法 新能源 API
路径规划-路线规划-驾车路径规划-步行路径规划-骑乘路径规划-公交路径规划API接口介绍
本文介绍地图路径规划API,支持驾车、步行、公交、骑行及电动车五种出行方式的智能路线计算。涵盖多策略算路(如避拥堵、少收费)、途经点/限行规避等高级功能,适用于无地图展示的线路查询或自研导航场景,助力开发者快速集成精准导航能力。
795 2
|
9月前
|
SQL 人工智能 自然语言处理
指标中台选型技术实测:如何通过 NoETL 语义层驾驭复杂 SQL 生成
支持“存量挂载、增量原生、存量替旧”的渐进式策略,平衡价值与风险,平滑实现架构升级。
|
10月前
|
弹性计算 运维 安全
阿里云CNAPP云安全中心全解析:优势、费用、合规及使用一文说透
阿里云CNAPP(智能云原生应用保护平台)整合CWPP、CSPM、CIEM与CTDR四大能力,提供覆盖“事前-事中-事后”的全链路安全防护。支持多云统一管理,内置380+检测模型,具备等保、ISO、PCI DSS等20+合规认证,助力企业实现一体化、智能化安全运营。免费版开放基础功能,高级版按需付费,新用户享15天全功能试用,快速构建云上安全防线。