动态规划 背包问题

news/发布时间2024/8/25 20:30:08

分类:01背包  完全背包

01: 多个物品,每个只有一个,物品有 weight 和value。背包载重有限制,问最多能放多少;

完全:多个物体,每个有无数个

dp[i][j] 的含义:在【0,i】这么多物品中,放入载重为 j 的背包内的最大价值。

物品/载重 载重0 载重1 载重2 载重3
物品0        
物品1        
物品2        
物品3        

 

递推式:dp[ i ] [ j ]= max( dp[ i-1 ] [ j -weight [ i ] ] + value[ i ] , dp[ i-1 ] [ j ]  )  -----  只与目标格的正上方以及左上方有关,所以初始化第一行和第一列, 其他的可以初始化为0;

初始化:只用初始化第一行,方法for (weight小于bagweight 则初始化为value)其他的初始化为多少都行,为方便初始化为0;

表格内填的是value;

 

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

如若内容造成侵权/违法违规/事实不符,请联系连锁易网进行投诉反馈email:xxxxxxxx@qq.com,一经查实,立即删除!

相关文章

Mac 上启用 root 用户

使用目录实用工具 使用“聚焦”查找并打开目录实用工具,或者按照以下步骤操作:从“访达”的菜单栏中,选取“前往”>“前往文件夹”。键入或粘贴 /System/Library/CoreServices/Applications/,然后按下回车键。从打开的窗口打开目录实用工具。启用或停用 root 用户 在“目…

了解hadoop

一:大数据 1:概念 就是巨大的数据,TB,EB,ZB,YB等,就是传统的数据库不能处理,具有海量的数据规模,快速的数据流转(实时性),多样的数据类型(从单一的变成了多种的),价值密度(多数据,并且有效数据多,利润价值大) 2:特征 大量:很多数据,并且一台计算机处理不…

ABC219 复盘

ABC219 复盘 [ABC219A] AtCoder Quiz 2 思路解析 直接判断 \(x\) 属于的区间然后输出即可。 时间复杂度:直接判断,\(O(1)\)。 code #include<bits/stdc++.h> using namespace std; int x; int main() {cin >> x;if(x < 40) cout << 40 - x; //直接判断即…

CPU型号后面的字母分别是什么含义?

笔记本CPU的处理器型号后缀U、P、H各自代表着不同的性能和用途。 U系列代表超低功耗(Ultra-Low Power),专为轻薄型笔记本电脑和长续航时间设备设计,适用于日常办公和轻度应用。 P系列则代表高性能(Performance),具备更高的时钟频率和计算能力,适用于复杂应用程序、多任…

Landsat 7的热红外波段有2个该如何选择?

本文介绍Landsat 7遥感影像数据中B61、B62两个热红外波段的区别,以及研究应用时二者选择的依据~本文介绍Landsat 7遥感影像数据中B61、B62两个热红外波段的区别,以及研究应用时二者选择的依据。Landsat 7遥感影像数据具有2个热红外波段,分别是Band 61与Band 62这两个波段;有…

PowerDesigner操作要点

一、PowerDesigner解决name和code同步问题 工具-常规选项-General Options-Dialog-Name to Code mirroring√去掉二、PowerDesigner用反向工程导入sql生成新的数据模型 1、文件-反向工程-Database 2、点击确定下一步 3、选择对应的SQL点击确定 4、结果如图所示 三、PowerD…

代码随想录算法训练营day18 | leetcode 513. 找树左下角的值、112(113). 路径总和(I、II)、105(106). 构造二叉树

目录题目链接:513. 找树左下角的值-中等题目链接:112. 路径总和-简单题目链接:113. 路径总和 II-中等题目链接:105. 从前序与中序遍历序列构造二叉树-中等题目链接:106. 从中序与后序遍历序列构造二叉树-中等 题目链接:513. 找树左下角的值-中等 题目描述: 给定一个二叉…

Jetbrains goland特性介绍

CLion 适用于 C 和 C++ 的跨平台 IDE CLion 消除了 C++ 中的大量工作,让我能够专注于有趣的部分:解决问题。 CLion 的新功能 CLion 2023.3采用 JetBrains AI Assistant,该助手现已超越技术预览阶段,带来更多上下文和项目感知操作,使您的日常 C++ 开发工作流程受益。新版本…

Jetbrains datagrip特性介绍

CLion 适用于 C 和 C++ 的跨平台 IDE CLion 消除了 C++ 中的大量工作,让我能够专注于有趣的部分:解决问题。 CLion 的新功能 CLion 2023.3采用 JetBrains AI Assistant,该助手现已超越技术预览阶段,带来更多上下文和项目感知操作,使您的日常 C++ 开发工作流程受益。新版本…

Jetbrains CLion特性介绍

CLion 适用于 C 和 C++ 的跨平台 IDE CLion 消除了 C++ 中的大量工作,让我能够专注于有趣的部分:解决问题。 CLion 的新功能 CLion 2023.3采用 JetBrains AI Assistant,该助手现已超越技术预览阶段,带来更多上下文和项目感知操作,使您的日常 C++ 开发工作流程受益。新版本…

从零开始学Spring Boot系列-集成mybatis

在Spring Boot的应用开发中,MyBatis是一个非常流行的持久层框架,它支持定制化SQL、存储过程以及高级映射。在本篇文章中,我们将学习如何在Spring Boot项目中集成MyBatis,以便通过MyBatis进行数据库操作。在Spring Boot的应用开发中,MyBatis是一个非常流行的持久层框架,它…

VMware Workstation 开启虚拟化引擎

摘要:想开启 VMware Workstation 虚拟机上的虚拟化引擎相关设置,却发现打不开。在网上一番搜集之后找到了解决办法。关闭 Windows 功能 打开 启用或关闭 Windows 功能,并关闭以下功能:Hyper-V Windows 沙盒 Windows 虚拟机监控程序平台 容器 适用于 Linux 的 Windows 子系统…

软件工程第一次作业(求大佬带

这个作业属于哪个课程 https://edu.cnblogs.com/campus/gdgy/SoftwareEngineering2024-dualdegree这个作业要求在哪里 [https://edu.cnblogs.com/campus/gdgy/SoftwareEngineering2024-dualdegree/homework/13146()这个作业的目标 熟悉markdown语言,阅读《构建之法》并回答五个…

亚马逊评级

在过去三个月,至少有41家券商机构给出过亚马逊评级,全部建议买入。对未来12个月的平均目标价预估为208.48美元,最高预估为230美元,最低预估为175美元。今年“七巨头”的表现之所以存在如此巨大的差异,一个被人们最广为提及的原因,无疑仍是AI……对投资者而言,像英伟达和…

基于EXO λ驱动的可编程分子信号传输架构和DNA电路中的反应物再生策略四节点DNA电路与EDRR。

为了解决过程中信号衰减的问题,利用独特的环形空间拓扑结构和EXO λ的水解特性,实现了EDRR策略 EXO λ的特性 如图1a所示,当EXO λ水解底物,锥形通道的宽端,可以从5 的钝端或凹端嵌入DNA链,从而连续和快速水解,在5 端有磷酸修饰的DNA链,而互补链则从锥形中穿出通道。它…

注销微博

没人会在意的, 喜欢你的人, 会主动联系你的, 不喜欢的人, 就算你主动联系, 也会觉得你很烦。 我真的尽力了。 简化自己的人生

Stream流

也叫做Stream流,是JDK8开始新增的一套API,用于操作集合或者数组的数据import java.util.ArrayList; import java.util.Arrays; import java.util.Collections; import java.util.List; import java.util.function.Consumer; import java.util.function.Predicate; import jav…

照片也能说话了?嘴型表情全同步,AI数字人时代要来了

SadTalker是一款先进的人工智能模型,它通过从音频中学习生成3D运动系数,并使用全新的三维面部渲染器来生成头部运动,只需传入一张照片和一段音频,就能生成高质量的AI数字人视频工作原理 1、显式地对音频和不同类型的运动系数之间的联系进行单独建模 2、通过蒸馏系数和3D渲染…

Windows MMC(Microsoft Management Console)的引入主要是为了解决以下几个问题

Windows MMC(Microsoft Management Console)的引入主要是为了解决以下几个问题:管理工具分散:在早期的Windows操作系统中,系统管理工具和控制面板中的设置项目比较分散,用户需要打开多个独立的应用程序来管理系统各个方面。这导致了管理效率低下和操作复杂。缺乏统一的管…

来说说看到的求职路上可以提高的地方——简历

要进行求职的时候应该遇到的第一件事情就是简历。 随着看到的简历越来越多,也发现了一些问题,来开个帖子来说说这些问题。 格式 让参加面试的人最头疼的地方就是简历格式没有空格。 最近发现好多人的简历格式上都不空格,很多内容完全都在一起,找起来特别费劲。 比如有求职者…
推荐文章