背包问题求方案数(一)

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

前言

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

本篇包括以下题目:

⭐️ AcWing 11. 背包问题求方案数

⭐️ AcWing 1023. 买书

⭐️ AcWing 1021. 货币系统

⭐️ AcWing 532. 货币系统


写博客有哪里不完善的地方或者有哪里表达错误希望大家提出来,博主会立即改正!望大家海涵


本文需要先自修基础:背包问题


注:本文中的所有代码全部为优化后的代码,且不提供优化解释,解释请见:背包问题,其中有详细的解释。

背包问题求方案数

题目要求

题目描述:

image.png

输入格式:

image.png

输出一个整数,表示 方案数 模109+7的结果。

数据范围:

image.png

输入样例:

4 5
1 2
2 4
3 4
4 6

输出样例:

2

思路分析

image.png

if (f[i][j] == f[i - 1][j]) 
   g[i][j] = (g[i][j] + g[i - 1][j]) % mol;
if (j >= v[i] && f[i][j] == f[i - 1][j - v[i]] + w[i]) 
   g[i][j] = (g[i][j] + g[i - 1][j - v[i]]) % mol; 

下面代码为一维优化后的代码

代码

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1010, mol = 1e9 + 7;
int f[N];
int g[N];
int main()
{
    int n, m;
    cin >> n >> m;
    g[0] = 1;
    for (int i = 1; i <= n; i ++ )
    {
        int v, w;
        cin >> v >> w;
        for (int j = m; j >= v; j -- )
        {
            int maxv = max(f[j], f[j - v] + w);
            int temp = 0;
            if (maxv == f[j]) temp = (temp + g[j]) % mol;
            if (maxv == f[j - v] + w) temp = (temp + g[j - v]) % mol;
            f[j] = maxv, g[j] = temp;
        }
    }
    int res = 0;
    for (int i = 0; i <= m; i ++ )
        if (f[i] == f[m])
            res = (res + g[i]) % mol;
    cout << res << endl;
    return 0;
}

买书

题目要求

题目描述:

小明手里有 n  元钱全部用来买书,书的价格为 10  元,20  元,50  元,100  元。

问小明有多少种买书方案?(每种书可购买多本)

输入格式:

一个整数 n,代表总共钱数。

输出格式:

一个整数,代表选择方案种数。

数据范围:

0≤n≤1000

输入样例1:

20

输出样例1:

2

输入样例2:

15

输出样例2:

0

输入样例3:

0

输出样例3:

1

思路分析

f[i]代表恰好用了 i 元钱的时候的方案数

代码

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1010;
int w[] = {10, 20, 50, 100};
int f[N];
int main()
{
    int n;
    cin >> n;
    f[0] = 1;
    for (int i = 0; i < 4; i ++ )
        for (int j = w[i]; j <= n; j ++ )
            f[j] += f[j - w[i]];
    cout << f[n] << endl;
    return 0;
}

思考

本题的 AC代码是先枚举的四种金钱,后枚举的体积,那么反过来是否可以呢?

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1010;
int w[] = {10, 20, 50, 100};
int f[N];
int main()
{
    int n;
    cin >> n;
    f[0] = 1;
    for (int i = 1; i <= n; i ++ )
        for (int j = 0; j < 4; j ++ )
            if (i >= w[j])
                f[i] += f[i - w[j]];
    cout << f[n] << endl;
    return 0;
}

答案是不可以!这是因为如果是第二种代码的话,会有重复计算的结果,比如花 30 元买书的话,第二种情况下,先花钱买一本 10 元的书、再花钱买一本 20元的书,和先花钱买一本 20  元的书、再花钱买一本 10元的书,这显然应该是一种情况的,但是却计算了两次。




目录
相关文章
|
监控 数据处理
基于STC89C52RC单片机的MODBUS RTU协议从机的实现
基于STC89C52RC单片机的MODBUS RTU协议从机的实现
1050 0
|
Prometheus 监控 Cloud Native
hyperf| hyperf/metric 上手指南
这期又开始聊微服务的基础设施之一: 实时监控. 更准确的说法, 基于 prometheus 的实时监控. 关于技术选型这里就不多啰嗦啦, 很多时候「从众」或者「用脚投票」往往是最有效的
1423 0
|
7月前
|
监控 Linux iOS开发
免费开源天花板!Veyon 机房多媒体教学管控全套部署 + 零基础实操教程
Veyon是一款完全免费、开源的跨平台教室控制软件,支持Windows/macOS/Linux,提供屏幕监控、广播、远程控制、文件分发等全功能,无需授权、无广告、无人数限制,轻松替代极域、红蜘蛛,是学校与培训机构的高性价比教学管控方案。
|
10月前
|
网络协议 安全
说一下 TCP 的三次握手四次挥手过程
我是小假 期待与你的下一次相遇 ~
845 1
|
10月前
|
人工智能 自然语言处理 自动驾驶
智能体来了:2026见证奇迹!AI元年核心爆发,你的数字分身已上线
内容摘要:2026年标志着AI从“对话框”跨入“全自动执行”的Agent时代。本文深度解析智能体(AI Agent)如何重塑生产力底层逻辑,拆解数字分身(Digital Twin)的核心技术路径,并提供普通人拥抱这一转型的实操建议,助你在AI元年抢占生存高地。
960 2
|
10月前
|
人工智能 监控 安全
从零到一搭建智慧工地平台:基于开源框架的快速定制开发与业务扩展实践
数字工地云平台融合物联网、AI、大数据与云计算,覆盖“人、机、料、法、环”全要素,提供人员/设备安全、视觉AI分析、扬尘监测、塔吊/升降机监控、深基坑预警等10+智能子系统,实现施工管理数字化、网络化、智慧化升级。
456 0
|
人工智能 Serverless API
10 分钟打造你的专属 AI 客服
在这个数字化时代,提供卓越的客户服务已成为企业脱颖而出的关键。为了满足这一需求,越来越多的企业开始探索人工智能(AI)助手的应用,以实现全天候(7x24)的客户咨询响应,全面提升用户体验和业务竞争力。本解决方案通过函数计算FC 和大模型服务平台百炼,为您提供一个高效便捷构建 AI 助手思路。
1469 43
|
人工智能 算法
AI+脱口秀,笑点能靠算法创造吗
脱口秀是一种通过幽默诙谐的语言、夸张的表情与动作引发观众笑声的表演艺术。每位演员独具风格,内容涵盖个人情感、家庭琐事及社会热点。尽管我尝试用AI生成脱口秀段子,但AI缺乏真实的情感共鸣和即兴创作能力,生成的内容显得不够自然生动,难以触及人心深处的笑点。例如,AI生成的段子虽然流畅,却少了那份不期而遇的惊喜和激情,无法真正打动观众。 简介:脱口秀是通过幽默语言和夸张表演引发笑声的艺术形式,AI生成的段子虽流畅但缺乏情感共鸣和即兴创作力,难以达到真人表演的效果。
SecureCRT 取消右击粘贴功能
SecureCRT 取消右击粘贴功能
1177 0