分组背包问题与背包问题求具体方案(一)

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

前言

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

本篇包括以下题目:

⭐️ AcWing 12. 背包问题求具体方案

⭐️ AcWing 9. 分组背包问题

⭐️ AcWing 1013. 机器分配

⭐️ AcWing 734. 能量石


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


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


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

背包问题求具体方案

题目要求

题目描述:

image.png

输入格式:

image.png

输出格式:

输出一行,包含若干个用空格隔开的整数,表示最优解中所选物品的编号序列,且该编号序列的字典序最小。

物品编号范围是 1 … N 。

数据范围:

image.png

输入样例:

4 5
1 2
2 4
3 4
4 6

输出样例:

1 4

思路分析

注意,因为要求输出的顺序是按照字典序,故我们在进行dp的过程中,枚举样本需要从大到小枚举,这样我们在按照字典序输出的时候就可以正向循环,查看状态i是由哪个状态j转移而来的 ( j > i )

代码

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

分组背包问题

题目要求

题目描述:

image.png

输入格式:

image.png

输出格式:

输出一个整数,表示最大价值。

数据范围:

image.png

输入样例:

3 5
2
1 2
2 4
1
3 4
1
4 5

输出样例:

8

思路分析

裸题,不解释,解释见博客:背包问题

代码

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




目录
相关文章
|
XML Android开发 数据格式
IDEA代码格式和JavaDoc设置,一键告别丑陋代码
IDEA代码格式和JavaDoc设置,一键告别丑陋代码
2670 1
IDEA代码格式和JavaDoc设置,一键告别丑陋代码
|
安全 Java 数据库
ifPresent()`方法的用途、使用场景
ifPresent()`方法的用途、使用场景
1736 4
|
存储 SQL 分布式计算
Hive存储表数据的默认位置详解
【8月更文挑战第31天】
2149 1
避开伤害——给金老师的留言
  看北理工金旭亮老师的博文好几年了。将一门课程建设到那种程度,我暂时“不务正业”更多些,我做做不到。   在如今的大学里,老师手里捧着宝贝,要传给学生,却时常遭遇软或硬的拒绝。这里面谁都没有错,但谁都可以做些事情去避免。当然,必有人受到伤害。我如今可以算是走出来不少了,当然也放下了一些自己不能承受的责任。   由于关注,看到了金老师的新作《一个不合时宜的人开的不合时宜的课》,特想留言,愿金老
1484 0
|
17天前
|
Linux 开发工具 iOS开发
Codex保姆级教程(下载+安装+登录+使用,含所有版本,2026最新)
Codex是OpenAI推出的开源AI编程智能体,本地运行,可理解整个代码库,支持自然语言指令改代码、执行命令、跑测试、修Bug,兼容Win/macOS/Linux。(239字)
7071 53
|
4天前
|
JSON 前端开发 API
阿里云最新Qwen4-Max大模型介绍:模型定位、特征、能力、适用场景解析
2026 年 11 月 11 日,阿里发布第四代旗舰模型Qwen4-Max预览版,首发千问 AI 平台 Token Plan,并同步接入千问办公、Qoder 等入口。该版本聚焦知识理解、世界感知、编程与 Agentic 四项升级,主打复杂编程、专业办公、前端设计与专业软件操作。预览期至 11 月 25 日 24:00,到期后模型标识下线;限时 2 折、新用户再享 5 折,最低 1 折可体验。
|
5天前
|
云安全 人工智能 安全
|
17天前
|
JavaScript API iOS开发
DeepSeek Harness下载、安装、配置一篇搞定(2026整理,送常用插件)
DeepSeek Harness(DSH)是DeepSeek于2026年开源的MIT协议AI Agent框架,支持插件化组装模型、工具、沙箱与UI,兼容主流大模型。本文提供免Node.js的桌面端安装包(Win/macOS),含详细图文教程及热门插件推荐。
5485 65