【背包问题 】01背包

目录

一，01背包问题详解

问题描述：

问题分析：

代码： 

空间优化：

二，典例

1，分割等和子集

题目解析： 

算法解析：

代码：

空间优化：

2，目标和

题目解析： 

算法解析：

代码： 

空间优化：

一，01背包问题详解

01背包问题是一种动态规划问题，动态规划问题的核心就是状态转移方程，本文主要讲述01背包问题。

本题链接：【模板】01背包_牛客题霸_牛客网

问题描述：

01背包问题可以描述如下：

        有一个容量为V的背包，还有n个物品。现在忽略物品的实际几何形状，我们认为只要背包的剩余容量大于物体体积，就可以装入该物品。且每个物品只能选一次或者不选。每个物品都有两个属性：体积v和价值w

         问：向背包中装入物品，不必装满和装满两种情况下的最大总价值时多少？

问题分析：

        首先，我们容易想到的是将状态表示定义为：dp[i]表示，以第i个商品为结尾，所能装的最大价值。而这样定义，就会面临一个问题，我们在装第i个物品时，不知道背包的剩余容量是否满足物品的体积。所以这个状态表示是不行的，我们可以再加上一个条件：

        dp[i][j]：以第i个物品为结尾，商品总体积不超过j，此时所能装的最大价值。

上述我们解决的时第一问，同样第二问也是如此，只是状态表示发生一点变化即可。 

          dp[i][j]：以第i个物品为结尾，商品总体积正好等于j，此时所能装的最大价值。

与第一问不同的是，我们想要正好凑成体积等于j的情况可能不存在，我们把这种状态的结果用-1来表示作区分。

代码： 

#include <iostream>
#include <string.h>

using namespace std;

const int N=1010;
int v[N],w[N];
int dp[N][N];

int main()
{
    int n,V;
    cin>>n>>V;

    for(int i=1;i<=n;i++)
    cin>>v[i]>>w[i];

    //第一问
    for(int i=1;i<=n;i++)
    for(int j=1;j<=V;j++)
    {
        dp[i][j]=dp[i-1][j];
        if(j>=v[i]) dp[i][j]=max(dp[i][j],dp[i-1][j-v[i]]+w[i]);
    }
    cout<<dp[n][V]<<endl;

    //第二问
    memset(dp,0,sizeof dp);
    for(int j=1;j<=V;j++)
    dp[0][j]=-1;

    for(int i=1;i<=n;i++)
    for(int j=1;j<=V;j++)
    {
        dp[i][j]=dp[i-1][j];
        if(j>=v[i]&&dp[i-1][j-v[i]]!=-1)
        dp[i][j]=max(dp[i][j],dp[i-1][j-v[i]]+w[i]);
    }
    cout<<(dp[n][V]==-1?0:dp[n][V])<<endl;

    return 0;
}

空间优化：

优化后代码：

#include <iostream>
#include <string.h>

using namespace std;

const int N=1010;
int v[N],w[N];
int dp[N];

int main()
{
    int n,V;
    cin>>n>>V;

    for(int i=1;i<=n;i++)
    cin>>v[i]>>w[i];
    //从右向左遍历dp，从左向右会被覆盖
    for(int i=1;i<=n;i++)
    for(int j=V;j>=v[i];j--)
    {
     dp[j]=max(dp[j],dp[j-v[i]]+w[i]);
    }
    cout<<dp[V]<<endl;

    memset(dp,0,sizeof dp);
    for(int j=1;j<=V;j++)
    dp[j]=-1;

    for(int i=1;i<=n;i++)
    for(int j=V;j>=v[i];j--)
    {
        if(dp[j-v[i]]!=-1)
        dp[j]=max(dp[j],dp[j-v[i]]+w[i]);
    }
    cout<<(dp[V]==-1?0:dp[V])<<endl;

    return 0;
}

二，典例

1，分割等和子集

题目链接：LCR 101. 分割等和子集 - 力扣（LeetCode）

题目解析： 

        判断一个数组是否可以分成元素和相等的两部分。

算法解析：

        本题的关键在于，是否可以做到问题的转化。对于一个数组我们可以知道它的所有元素的和sum,那么我们就可以得到这两部分元素的和都为sum/2。而我们只要知道一个数组是否可以凑成sum/2，如果可以，那么该数组就可以分成元素相等的两部分，返回true。否则返回false。

        这样我们就把问题转化成了一个数组是否可以凑成sum/2，数组相当于物品，背包容量为sum/2，从数组中选取元素，装入背包。

 

代码：
class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int n=nums.size();
        int sum=0;
        for(int x:nums) sum+=x;
        if(sum%2)
        return false;

        vector<vector<bool>> dp(n+1,vector<bool>(sum/2+1));
        for(int i=0;i<=n;i++)
        dp[i][0]=true;

        for(int i=1;i<=n;i++)
        for(int j=1;j<=sum/2;j++)
        {
            dp[i][j]=dp[i-1][j];
            if(j>=nums[i-1])
            dp[i][j]=dp[i][j]||dp[i-1][j-nums[i-1]];
        }
        return dp[n][sum/2];


    }
};
空间优化：
class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int n=nums.size();
        int sum=0;
        for(int x:nums) sum+=x;
        if(sum%2) return false;

        int aim=sum/2;
        vector<bool> dp(aim+1);
        dp[0]=true;
        for(int i=1;i<=n;i++)
        for(int j=aim;j>=nums[i-1];j--)
        dp[j]=dp[j]||dp[j-nums[i-1]];

        return dp[aim];
    }
};

2，目标和

题目链接：LCR 102. 目标和 - 力扣（LeetCode）

题目解析： 

        向一个整数数组nums的元素前加'+'或者'-'，产生的表达式，使其运算后的值等于目标和target，求不同表达式的数目。

算法解析：

        与上题一样，本题的关键在于第一步的问题转化。同样，对于一个数组，我们可以求出所有元素的和sum。题目描述，我们可以在元素前添上+/-，那么这个数组就可以被分成两部分，一部分是所有元素都是正的，另一部分的元素都是负的，假设所有元素都是正数的这部分和为a，而所有元素都是负数的和为b（b是这部分元素和的绝对值，b是大于0的）。

        那么就可以得到a+b=sum，同时如果满足题目要求，可以得到a-b=target。联立可以得到

a=(target+sum)/2，target和sum都是已知的。此时，问题就转化成了，是否可以在数组中找到和正好等于a的不同选法。

代码： 
class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        int aim=0,sum=0;
        int n=nums.size();
        for(auto& x:nums)
        sum+=x;
        aim=(target+sum)/2;
        if(aim<0||(target+sum)%2)
        return 0;
        vector<vector<int>> dp(n+1,vector<int>(aim+1));
        dp[0][0]=1;
        for(int i=1;i<=n;i++)
        for(int j=0;j<=aim;j++)
        {
            dp[i][j]=dp[i-1][j];
            if(j>=nums[i-1])
            dp[i][j]+=dp[i-1][j-nums[i-1]];
        }
        return dp[n][aim];
    }
};
空间优化：
class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        int aim=0,sum=0;
        int n=nums.size();
        for(auto& x:nums)
        sum+=x;
        aim=(target+sum)/2;
        if(aim<0||(target+sum)%2)
        return 0;
        vector<int> dp(aim+1);
        dp[0]=1;
        for(int i=1;i<=n;i++)
        for(int j=aim;j>=nums[i-1];j--)
        {
            dp[j]+=dp[j-nums[i-1]];
        }
        return dp[aim];
    }
};

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/959625.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

81，【5】BUUCTF WEB [b01lers2020]Life on Mars

81，【5】BUUCTF WEB [b01lers2020]Life on Mars

进入靶场 怎莫颠颠的&#xff0c;一下子就想到展博了 先把左边的挨个点一遍 在最后一个有点收获 不过也没其他收获了 这种进去给个正常网页的题目&#xff0c;基本都靠url获取信息了 抓包看看有没有其他信息 竟然没有任何信息 自闭了 看别人的wp去咯 为什么别人抓到的包里…
阅读更多...
80，【4】BUUCTF WEB [SUCTF 2018]MultiSQL

80，【4】BUUCTF WEB [SUCTF 2018]MultiSQL

53&#xff0c;【3】BUUCTF WEB october 2019 Twice SQLinjection-CSDN博客 上面这个链接是我第一次接触二次注入 这道题也涉及了 对二次注入不熟悉的可以看看 BUUCTF出了点问题&#xff0c;打不开&#xff0c;以下面这两篇wp作为学习对象 [SUCTF 2018]MultiSQL-CSDN博客 …
阅读更多...
Vue 响应式渲染 - 指令

Vue 响应式渲染 - 指令

Vue 渐进式JavaScript 框架 基于Vue2的学习笔记 - Vue 响应式渲染 - 指令 目录 指令 介绍 缩写 指令示例 总结 指令 介绍 指令&#xff1a;是指带有v-前缀的特殊属性 v-bind 动态绑定属性 v-if 动态创建/删除 v-show 动态显示/隐藏 v-on:click 绑定事件 v-for 遍历…
阅读更多...
扣子平台音频功能：让声音也能“智能”起来

扣子平台音频功能：让声音也能“智能”起来

在数字化时代&#xff0c;音频内容的重要性不言而喻。无论是在线课程、有声读物&#xff0c;还是各种多媒体应用&#xff0c;音频都是传递信息、增强体验的关键元素。扣子平台的音频功能&#xff0c;为开发者和内容创作者提供了一个强大而灵活的工具&#xff0c;让音频的使用和…
阅读更多...
python3+TensorFlow 2.x（三）手写数字识别

python3+TensorFlow 2.x（三）手写数字识别

目录 代码实现 模型解析&#xff1a; 1、加载 MNIST 数据集&#xff1a; 2、数据预处理&#xff1a; 3、构建神经网络模型&#xff1a; 4、编译模型&#xff1a; 5、训练模型&#xff1a; 6、评估模型&#xff1a; 7、预测和可视化结果&#xff1a; 输出结果&#xff…
阅读更多...
LKT4304新一代算法移植加密芯片，守护 物联网设备和云服务安全

LKT4304新一代算法移植加密芯片，守护 物联网设备和云服务安全

凌科芯安作为一家在加密芯片领域深耕18年的企业&#xff0c;主推的LKT4304系列加密芯片集成了身份认证、算法下载、数据保护和完整性校验等多方面安全防护功能&#xff0c;可以为客户的产品提供一站式解决方案&#xff0c;并且在调试和使用过程提供全程技术支持&#xff0c;针对…
阅读更多...
js/ts数值计算精度丢失问题及解决方案

js/ts数值计算精度丢失问题及解决方案

文章目录 概念及问题问题分析解决方案方案一方案二方案其它——用成熟的库 概念及问题 js中处理浮点数运算时会出现精度丢失。js中整数和浮点数都属于Number数据类型&#xff0c;所有的数字都是以64位浮点数形式存储&#xff0c;整数也是如此。所以打印x.00这样的浮点数的结果…
阅读更多...
SSM框架探秘：Spring 整合 SpringMVC 框架

SSM框架探秘：Spring 整合 SpringMVC 框架

搭建和测试 SpringMVC 的开发环境&#xff1a; web.xml 元素顺序&#xff1a; 在 web.xml 中配置 DisPatcherServlet 前端控制器&#xff1a; <!-- 配置前端控制器 --> <servlet><servlet-name>dispatcherServlet</servlet-name><servlet-class>…
阅读更多...
算法11（力扣496）-下一个更大元素I

算法11（力扣496）-下一个更大元素I

1、问题 nums1 中数字 x 的 下一个更大元素 是指 x 在 nums2 中对应位置 右侧 的 第一个 比 x 大的元素。 给你两个 没有重复元素 的数组 nums1 和 nums2 &#xff0c;下标从 0 开始计数&#xff0c;其中nums1 是 nums2 的子集。 对于每个 0 < i < nums1.length &#xf…
阅读更多...
2024年博客之星主题创作|2024年蓝桥杯与数学建模年度总结与心得

2024年博客之星主题创作|2024年蓝桥杯与数学建模年度总结与心得

引言 2024年&#xff0c;我在蓝桥杯编程竞赛和数学建模竞赛中投入了大量时间和精力&#xff0c;这两项活动不仅加深了我对算法、数据结构、数学建模方法的理解&#xff0c;还提升了我的解决实际问题的能力。从蓝桥杯的算法挑战到数学建模的复杂应用&#xff0c;我在这些竞赛中…
阅读更多...
Spring FatJar写文件到RCE分析

Spring FatJar写文件到RCE分析

背景 现在生产环境部署 spring boot 项目一般都是将其打包成一个 FatJar&#xff0c;即把所有依赖的第三方 jar 也打包进自身的 app.jar 中&#xff0c;最后以 java -jar app.jar 形式来运行整个项目。 运行时项目的 classpath 包括 app.jar 中的 BOOT-INF/classes 目录和 BO…
阅读更多...
初阶数据结构：链表（二）

初阶数据结构：链表（二）

目录 一、前言 二、带头双向循环链表 1.带头双向循环链表的结构 &#xff08;1)什么是带头&#xff1f; (2)什么是双向呢&#xff1f; &#xff08;3&#xff09;那什么是循环呢&#xff1f; 2.带头双向循环链表的实现 &#xff08;1&#xff09;节点结构 &#xff08;2…
阅读更多...
Java Web-Request与Response

Java Web-Request与Response

在 Java Web 开发中&#xff0c;Request 和 Response 是两个非常重要的对象&#xff0c;用于在客户端和服务器之间进行请求和响应的处理&#xff0c;以下是详细介绍&#xff1a; Request&#xff08;请求对象&#xff09; Request继承体系 在 Java Web 开发中&#xff0c;通…
阅读更多...
mysql 学习2 MYSQL数据模型，mysql内部可以创建多个数据库，一个数据库中有多个表；表是真正放数据的地方，关系型数据库 。

mysql 学习2 MYSQL数据模型，mysql内部可以创建多个数据库，一个数据库中有多个表；表是真正放数据的地方，关系型数据库 。

在第一章中安装 &#xff0c;启动mysql80 服务后&#xff0c;连接上了mysql&#xff0c;那么就要 使用 SQL语句来 操作mysql数据库了。那么在学习 SQL语言操作 mysql 数据库 之前&#xff0c;要对于 mysql数据模型有一个了解。 MYSQL数据模型 在下图中 客户端 将 SQL语言&…
阅读更多...
微信小程序date picker的一些说明

微信小程序date picker的一些说明

微信小程序的picker是一个功能强大的组件&#xff0c;它可以是一个普通选择器&#xff0c;也可以是多项选择器&#xff0c;也可以是时间、日期、省市区选择器。 官方文档在这里 这里讲一下date picker的用法。 <view class"section"><view class"se…
阅读更多...
【学习笔记】计算机网络（二）

【学习笔记】计算机网络（二）

第2章 物理层 文章目录 第2章 物理层2.1物理层的基本概念2.2 数据通信的基础知识2.2.1 数据通信系统的模型2.2.2 有关信道的几个基本概念2.2.3 信道的极限容量 2.3物理层下面的传输媒体2.3.1 导引型传输媒体2.3.2 非导引型传输媒体 2.4 信道复用技术2.4.1 频分复用、时分复用和…
阅读更多...
总结8..

总结8..

#include <stdio.h> // 定义结构体表示二叉树节点&#xff0c;包含左右子节点编号 struct node { int l; int r; } tree[100000]; // 全局变量记录二叉树最大深度&#xff0c;初始为0 int ans 0; // 深度优先搜索函数 // pos: 当前节点在数组中的位置&#xff0c…
阅读更多...
多智能体中的理论与传统智能体理论有何异同?

多智能体中的理论与传统智能体理论有何异同?

多智能体系统与传统单智能体理论在多个方面存在异同&#xff0c;多智能体系统在理论上扩展了单智能体系统的研究范畴&#xff0c;强调智能体之间的交互和协作。随着人工智能、人机智能、人机环境系统智能的发展&#xff0c;多智能体系统在机器人群体、分布式计算、资源管理等领…
阅读更多...
RKNN_C++版本-YOLOV5

RKNN_C++版本-YOLOV5

1.背景 为了实现低延时&#xff0c;所以开始看看C版本的rknn的使用&#xff0c;确实有不足的地方&#xff0c;请指正&#xff08;代码借鉴了rk官方的仓库文件&#xff09;。 2.基本的操作流程 1.读取模型初始化 // 设置基本信息 // 在postprocess.h文件中定义&#xff0c;详见…
阅读更多...
FlinkSql使用中rank/dense_rank函数报错空指针

FlinkSql使用中rank/dense_rank函数报错空指针

问题描述 在flink1.16(甚至以前的版本)中&#xff0c;使用rank()或者dense_rank()进行排序时&#xff0c;某些场景会导致报错空指针NPE(NullPointerError) 报错内容如下 该报错没有行号/错误位置&#xff0c;无法排查 现状 目前已经确认为bug&#xff0c;根据github上的PR日…
阅读更多...
最新文章

Copyright @ 2022~2023