动态规划- 背包问题总结(二)

简介: 动态规划- 背包问题总结(二)

什么是动态规划

动态规划通过额外的空间将已经搜索过的相似的结果(指某些具有相同性质解的集合)用一个数组存起来,所以DP中的状态转移看上去是某两三个值之间的推导,其实是某两三个集合之间的状态转移!

常见的背包模型

  1. 01背包问题
  2. 完全背包问题
  3. 多重背包问题
  4. 分组背包问题

传送们:动态规划- 背包问题总结(一)

多重背包模型

典型题例:

有 N 种物品和一个容量是 V 的背包。

第 i 种物品最多有 si 件,每件体积是 vi,价值是 wi。

求解将哪些物品装入背包,可使物品体积总和不超过背包容量,且价值总和最大。

输出最大价值。

示例 :

输入:第一行两个整数,N,V,用空格隔开,分别表示物品种数和背包容积。
      接下来有 N 行,每行三个整数 vi,wi,si,用空格隔开,分别表示第 i 种物品的体积、价值和数量。
4 5
1 2 3
2 4 1
3 4 3
4 5 2

思路

与01背包 完全背包最后集合的划分,也就是状态计算不太一样。
最后的状态划分为第i个选0~k个的情况

代码:

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 110;
int n, m;
int f[N];
int main() {
    cin >> n >> m;
    for (int i = 0; i < n; i ++) {
        int v, w, s;
        cin >> v >> w >> s;
        for (int j = m; j >= 0; j --) 
            for (int k = 1; k <= s && k * v <   = j; k ++)  //优化:选的个数*体积<总体积
                f[j] = max(f[j], f[j - k * v] + k * w);
    }
    cout << f[m] << endl;
    return 0;
}

分组背包问题

典型题例:

有 N 组物品和一个容量是 V 的背包。

每组物品有若干个,同一组内的物品最多只能选一个。

每件物品的体积是 vij,价值是 wij,其中 i 是组号,j 是组内编号。

求解将哪些物品装入背包,可使物品总体积不超过背包容量,且总价值最大。

输出最大价值。

示例 :

输入:第一行有两个整数 N,V,用空格隔开,分别表示物品组数和背包容量。
接下来有 N 组数据:
1)每组数据第一行有一个整数 Si,表示第 i 个物品组的物品数量;
2)每组数据接下来有 Si 行,每行有两个整数 vij,wij,用空格隔开,分别表示第 i 个物品组的第 j 个物品的体积和价值;
3 5
2
1 2
2 4
1
3 4
1
4 5
输出:
8

思路

与多重背包问题相似,多重背包问题时分组背包问题的个例

代码:

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 110;
int n, m;
int f[N]; //
int v[N], w[N], s[N];  //s[i]第i组物品的个数
int main() {
    cin >> n >> m;
    for (int i = 0; i < n; i ++) {  //枚举组别
        int s = 0;
        cin >> s;
        //循环输入每组中的物品的体积和价值
        for (int j = 0; j < s; j ++) cin >> v[i] >> w[i];
        for (int j = m; j >= 0; j --)  //
            for (int k = 0; k < s; k ++)  //枚举每组中的一个物品
                if (j >= v[k]) 
                    f[j] = max(f[j], f[j - v[k]] + w[k]);
    }
    cout << f[m] << endl;
    return 0;
}

充电站

推荐一个零声学院免费公开课程,个人觉得老师讲得不错,分享给大家:Linux,Nginx,ZeroMQ,MySQL,Redis,fastdfs,MongoDB,ZK,流媒体,CDN,P2P,K8S,Docker,TCP/IP,协程,DPDK等技术内容,立即学习

相关文章
|
存储 安全 算法
什么是量子安全?量子计算时代下的基本安全技术
什么是量子安全?量子计算时代下的基本安全技术
1203 0
|
6天前
|
Linux Go 开发工具
手机上跑 DeepSeek 智能体:开源安卓客户端 DSH Go 安装与使用指南
DSH Go 是一款开源安卓客户端,将 DeepSeek Harness 智能体引擎装进手机:免 Root、免 Termux,一键安装即用;支持本机运行(内置 Ubuntu+Node.js)或远程接管电脑会话;具备插话打断、过程折叠、屏幕操控、端到端加密分享等特色功能,真正实现智能体“口袋化”。
7059 17
|
6天前
|
弹性计算 人工智能 API
Codex超详细入门指南(下载·安装·登录·上手,全版本覆盖,2026最新版)
建议收藏本教程,2026 全年各版本更新随时回来查阅。如果你在搭建过程中遇到任何问题,欢迎结合 阿里云工单系统 提交技术支持请求,或在 阿里云开发者社区 搜索 Codex 相关话题交流。 祝你编码愉快,效率翻倍!
2334 10
|
8天前
|
人工智能 前端开发 API
阿里云Qwen4-Max 大模型详解:定位、特征、能力、适用场景与相对Qwen3-Max差异解析
2026年11月11日,阿里发布第四代旗舰模型Qwen4-Max预览版,首发千问AI平台Token Plan并接入千问办公、Qoder等入口。该版本聚焦知识理解、世界感知、编程与Agentic四项升级,主打复杂编程、专业办公、前端设计与专业软件操作等真实任务。预览期为11月11日10:00至11月25日24:00,仅支持Token Plan调用,到期后模型标识下线;限时2折、新用户再享5折,最低1折可体验。
|
8天前
|
JSON 前端开发 API
阿里云最新Qwen4-Max大模型介绍:模型定位、特征、能力、适用场景解析
2026 年 11 月 11 日,阿里发布第四代旗舰模型Qwen4-Max预览版,首发千问 AI 平台 Token Plan,并同步接入千问办公、Qoder 等入口。该版本聚焦知识理解、世界感知、编程与 Agentic 四项升级,主打复杂编程、专业办公、前端设计与专业软件操作。预览期至 11 月 25 日 24:00,到期后模型标识下线;限时 2 折、新用户再享 5 折,最低 1 折可体验。
|
4天前
|
传感器 安全 区块链
Windows 电脑运行安卓应用教程:开源工具 ApkStart 双击 APK 即装、独立窗口运行
ApkStart 是一款开源Windows工具,让安卓APP像原生软件一样运行:双击APK即安装、生成真实图标、独立窗口启动、开始菜单可搜索。无需传统模拟器,内置QEMU运行时,支持数据互通、ARM兼容与命令行操作。(239字)
|
21天前
|
Linux 开发工具 iOS开发
Codex保姆级教程(下载+安装+登录+使用,含所有版本,2026最新)
Codex是OpenAI推出的开源AI编程智能体,本地运行,可理解整个代码库,支持自然语言指令改代码、执行命令、跑测试、修Bug,兼容Win/macOS/Linux。(239字)
10222 59
|
4天前
|
人工智能 弹性计算 开发工具
零成本玩各大模型!DeepSeek Harness dsh-our-free-model 插件,13 个厂商模型直接用
总结一下:装这个插件,你不用注册、不用绑卡、不用填一个 Key,就能在 DeepSeek Harness 里用上 DeepSeek V4.1 Flash、Kimi K3 这一批前沿模型,而且是白嫖的、还不限量。三步搞定:下载插件,复制包含 `package.json` 的插件目录路径,在「添加插件」里粘贴路径安装并重启。无论是在阿里云 ECS 上通过命令行部署的 Web 版,还是本地的 Electron 桌面端,都能顺利跑通,快速搭建一套零成本的免费模型使用环境。
1058 1