背包问题求方案数(一)

简介: 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,代表总共钱数。

输出格式:

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

数据范围:

0n1000

输入样例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元的书,这显然应该是一种情况的,但是却计算了两次。




目录
相关文章
|
10月前
|
存储 编译器 C语言
【C语言】指针大小知多少 ?一场探寻C语言深处的冒险 !
在C语言中,指针的大小(即指针变量占用的内存大小)是由计算机的体系结构(例如32位还是64位)和编译器决定的。
1198 9
|
前端开发 JavaScript 数据处理
.单页面应用和多页面应用区别及优缺点
.单页面应用和多页面应用区别及优缺点
430 4
|
存储 Ubuntu Linux
Docker容器简介、优缺点与安装
Docker容器简介、优缺点与安装
|
存储 弹性计算 运维
|
安全 Java 应用服务中间件
|
JavaScript 前端开发 CDN
vue-video-player基本使用
vue-video-player 是基于vue的 视频播放器,可以便捷的适配到项目中
1113 1
|
开发框架 缓存 Java
盘古开发框架简介,工业级微服务开发治理框架
「盘古开发框架」是一套轻量灵活、成熟可靠的工业级分布式微服务开发和治理框架(兼容垂直单体分层架构)。它基于 Apache-2.0 协议开源发布,且是免费的。
1270 1
盘古开发框架简介,工业级微服务开发治理框架
|
监控 网络协议 安全
VoIP系统故障排除:7个常见问题处理方法
VoIP呼叫已成为世界各地公司的主要通信方式。事实上,2020年美国的VoIP服务市场规模约为71亿美元。
|
前端开发 JavaScript 数据安全/隐私保护
5款非常优秀的基于 vue3.x 和 Native UI 的中后台管理系统模板
5款非常优秀的基于 vue3.x 和 Native UI 的中后台管理系统模板
3244 0
5款非常优秀的基于 vue3.x 和 Native UI 的中后台管理系统模板