01背包补题(一)(上)

简介: 01背包补题(一)

前言

动态规划——01背包的一些习题,包含如下题目:

⭐️ P1048 采药

⭐️ P2871 [USACO07DEC]Charm Bracelet S

⭐️ P1049 装箱问题

⭐️ P1060 开心的金明

⭐️ P1164 小A点菜

⭐️ P1510 精卫填海

⭐️ P2639 [USACO09OCT]Bessie’s Weight Problem G

⭐️ P2925 [USACO08DEC]Hay For Sale S

⭐️ P1926 小书童——刷题大军

⭐️ P1802 5倍经验日

⭐️ P1734 最大约数和

⭐️ P2392 kkksc03考前临时抱佛脚


刷题记录,不提供代码解释,01背包的讲解博客见:01背包问题及二维费用背包问题

P1048 [NOIP2005 普及组] 采药

本题链接:P1048 [NOIP2005 普及组] 采药

本博客给出本题截图:

54.png


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

P2871 [USACO07DEC]Charm Bracelet S

本题链接:P2871 [USACO07DEC]Charm Bracelet S

本博客给出本题截图:

55.png

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

P1049 [NOIP2001 普及组] 装箱问题

本题链接:P1049 [NOIP2001 普及组] 装箱问题

本博客给出本题截图:

56.png

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

P1060 [NOIP2006 普及组] 开心的金明

本题链接:P1060 [NOIP2006 普及组] 开心的金明

本博客给出本题截图:

57.png

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



目录
相关文章
|
8月前
|
人工智能 API
阿里云 AI 通用节省计划和 Coding Plan有什么区别?OpenClaw 省钱攻略全解
阿里云AI通用节省计划是预付费模式,承诺每小时最低消费享折扣,不退订、超支另计费;百炼Coding Plan为月度资源包,按请求量(如Token)计费,用完即停、不超支,仅限指定模型。OpenClaw推荐优先选Coding Plan控成本。
2204 2
|
数据挖掘 测试技术 图形学
《3D动作游戏受击反馈:从模板化硬直到沉浸式打击感的开发拆解》
本文记录3D动作游戏角色受击反馈系统的开发实践,针对早期依赖引擎模板导致的反馈雷同、硬直僵化等问题展开优化。通过联合多岗位梳理“视觉差异化、物理动态化、音效分层”需求,放弃传统组件,自研受击反馈状态机,实现状态独立配置与优先级切换;构建伤害类型-反馈参数映射表适配不同场景,开发动态硬直判定器平衡攻防体验。经性能优化(特效实例化、粒子分级)与细节打磨(弱点反馈强化、残血感知优化),解决卡顿、反馈不清晰等痛点,最终实现“每一击有重量”的沉浸打击感,为动作游戏受击系统开发提供实用参考。
1216 11
|
监控 ice
如何用简单步骤实现合约量化策略盈利
成果定义、MVP拆解、分步执行模板、异常应对、量化迭代与规模化交付六步法,系统化推进量化策略从实验到生产落地,确保可控、可复现、可扩展。
|
存储 人工智能 弹性计算
WordPress AI助手操作
本文将介绍如何使用阿里云百炼平台创建知识库与AI助手应用,包括数据上传、模型配置、应用部署及资源清理等步骤,并详细说明了如何在Web页面集成AI助手悬浮框,实现智能对话功能。
956 5
|
11月前
|
存储 Java 编译器
Java泛型类型擦除以及类型擦除带来的问题
本文详解Java泛型的类型擦除机制及其带来的问题。介绍泛型擦除后保留的原始类型、编译时类型检查原理、自动类型转换、与多态的冲突、静态成员限制等核心问题,并结合代码示例说明其底层实现和解决方案,帮助深入理解Java泛型的本质与局限性。(238字)
|
11月前
|
人工智能 算法 数据可视化
别卷手工测试了!这6个大模型应用场景让你身价翻倍
大语言模型正重塑软件测试:从AI生成用例、智能代码审查到需求深度解析,推动测试自动化、智能化升级。测试工程师需掌握AI协同技能,聚焦高阶质量设计,实现职业跃迁。
|
机器学习/深度学习 算法 数据挖掘
足球比赛的镜头如何变成数据:从视频分析到实时数据应用
足球视频分析利用计算机视觉与深度学习技术,将比赛镜头转化为球员位置、动作及赛事事件等结构化数据,助力战术制定、表现评估与观赛体验升级,推动体育智能化发展。
|
编解码 监控
使用OBS Studio进行多路直播时,有哪些高级设置可以优化同步性?
使用OBS Studio进行多路直播时,有哪些高级设置可以优化同步性?
|
Java 索引
Java ArrayList中的常见删除操作及方法详解。
通过这些方法,Java `ArrayList` 提供了灵活而强大的操作来处理元素的移除,这些方法能够满足不同场景下的需求。
899 30
|
SQL 移动开发 前端开发
ruoyi-nbcio从spring2.7.18升级springboot到3.1.7,java从java8升级到17(一)
ruoyi-nbcio从spring2.7.18升级springboot到3.1.7,java从java8升级到17(一)
921 0