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

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

什么是动态规划

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

常见的背包模型

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

01背包问题

典型题例:

有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。

第 i 件物品的体积是 vi,价值是 wi。

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

输出最大价值。

示例 :

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

思路

代码:

朴素做法:

#include <iostream>
using namespace std;
const int N = 1010;
int n, m;
int v[N], w[N];
int f[N][N];
int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i ++) cin >> v[i] >> w[i];
    for (int i = 1; i <=n; i ++)
        for (int j = 0; j <= m; j ++) {
            f[i][j] = f[i - 1][j];  //所有不选i的集合(左边集合)
            //  当前背包容量装不进第i个物品,则价值等于前i-1个物品
            if (j >= v[i]) f[i][j] = max(f[i][j], f[i -1][j - v[i]] + w[i]);
        }
    cout << f[n][m] << endl;
    return 0;
}

空间优化-等式变形

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

完全背包问题

典型题例:

有 N 种物品和一个容量是 V 的背包,每种物品都有无限件可用。

第 i 种物品的体积是 vi,价值是 wi。

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

输出最大价值。

示例 :

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

思路

代码:

朴素做法

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

优化

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

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

充电站

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

相关文章
|
JavaScript 前端开发
JavaScript实现11位手机号码正则表达式
JavaScript实现11位手机号码正则表达式
718 0
|
存储 数据管理 关系型数据库
分布式系统设计之套路Master-Slave架构
分布式系统设计之套路Master-Slave架构
2241 0
|
1月前
|
存储 弹性计算 固态存储
阿里云服务器价格:轻量38元1年、ECS云服务器99元和199元配置指南
2026年阿里云服务器最新报价:轻量应用服务器低至38元/年(2核2G、200M峰值带宽、不限流量);ECS经济型e实例99元/年起,企业级c9i/g9i/r9i等规格丰富,支持包年包月、按量付费等多种计费模式。
248 0
|
1月前
|
人工智能 自然语言处理 算法
AI面试八股文-01_1-LLM基础概念(Token-上下文窗口-幻觉)
本PDF详解LLM核心概念:Token本质与中英文差异、Temperature/Top-P等采样参数、上下文窗口现状(含GPT-6/Claude 5/Qwen 3.8等2026年最新模型)、幻觉治理、涌现能力与灾难性遗忘,并对比BPE与SentencePiece分词原理。
|
1月前
|
人工智能 数据库 开发者
美国爆款App换个国家重做:11个月从月入1千到8万美金,他复制的不是产品是机会
本文是「OPC一人公司通关手册」第34篇,拆解一个真实高效的AI创业案例:23岁以色列营销人,零代码、单人操盘,用AI工具两周上线希伯来语卡路里App,11个月内月收入从1千美元跃升至8万美元(约57万人民币),全程技术成本仅355美元/月。核心模式是“本地化套利”——复用美国已验证需求,深度适配语言、食物库与本地营销素材,并以分成制撬动网红资源。方法可复制,数字需理性参考。(239字)
|
1月前
|
存储 弹性计算 安全
阿里云服务器租用流程解析:自定义/快速/活动/云市场四种主流租用流程详解
阿里云云服务器租用分为四条主流方式:自定义租用控制粒度最细,可逐项配置计费模式、地域、实例规格、镜像、存储、带宽与安全组;一键部署适合快速交付与开发测试,但默认不含数据盘、需自行配置安全组;云市场镜像提供开箱即用的软件环境,需核验兼容性与第三方安全更新;限时活动购买性价比最高,如轻量2核2G 38元/年、经济型e 99元/年、u1 2核4G 199元/年。选型应兼顾业务负载、续费政策与账号资格。
|
2月前
|
人工智能 自然语言处理 搜索推荐
企业如何应用智能客服提升转化率?实战案例深度解析
电商客服面临咨询高峰流失、重复问题低效、系统割裂三大困局。阿里云瓴羊Quick Service以AI Agent为核心,实现“能答”到“能办”跃升:直连订单物流系统、自动完成退换货等操作,压缩60%处理时长;支持全渠道统一接入与人机协同,实测转化率提升8.39%,转人工率降45%。
|
2月前
|
JSON 监控 安全
简电云 | OCPP 1.6、OCPP 2.0.1 与 OCPP 2.1 有什么区别?一篇文章讲清协议演进与技术选型
本文从研发与架构视角深度解析OCPP 1.6、2.0.1、2.1三大版本差异,涵盖设备模型、交易状态机、安全体系、智能充电、双向充放电、ISO 15118、支付及换电等核心能力演进,强调版本间非简单兼容,升级需重构数据模型与状态逻辑。
|
7月前
|
安全 前端开发 Java
SpringBoot注解参数校验,给代码穿上“防弹衣”
SpringBoot的注解校验就像给你的方法参数请了个私人保镖,专门拦截那些不靠谱的输入。没有它?用户传个`null`过来,你的程序可能就会表演“当场崩溃”的绝活。
276 3
|
8月前
|
人工智能 Linux API
每天省2小时!阿里云/本地保姆级部署OpenClaw+飞书集成+百炼API配置完整指南
2026年的职场办公,真正的效率提升从不是靠加班硬拼,而是把机械重复的“后台工作”交给AI,把精力留给核心的思考与决策。OpenClaw作为实干型AI生产力工具,与飞书的深度融合,让这份想象成为现实——从数据汇总、文件信息提取,到资料分发、周报生成,原本耗时数小时的机械劳动,AI十秒就能完成,每周至少为职场人省出3.5小时。本文将拆解OpenClaw+飞书的4大核心办公提效场景,给出可直接落地的操作方法,同时完整整理2026年OpenClaw在阿里云及本地MacOS/Linux/Windows11的部署流程、阿里云百炼Coding Plan免费大模型API配置步骤,以及部署和集成中的常见问题解
1070 6