01背包问题+完全背包问题+多重背包问题+多重背包问题+分组背包问题

文章目录

  • 01背包问题
  • 完全背包问题
  • 多重背包问题 I
  • 多重背包问题 II
  • 分组背包问题

01背包问题

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

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

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

输入格式

第一行两个整数,N,V,用空格隔开,分别表示物品数量和背包容积。

接下来有 N 行,每行两个整数 vi,wi,用空格隔开,分别表示第 i 件物品的体积和价值。

输出格式

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

数据范围

0<N,V≤1000
0< vi,wi≤1000

输入样例

4 5
1 2
2 4
3 4
4 5

输出样例:

8

未优化思路:时间复杂度O(mn) 100w,空间复杂度 4B*1000000/1024/1024=4MB

#include<bits/stdc++.h>
using namespace std;
const int N = 1e3+10;
//f[i][j]表示选前i个物品中,剩余体积是j的最大容量。
int f[N][N],v[N],w[N];
int n,m;

int main(){
   
    cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>v[i]>>w[i];
    //默认初始化f[0][0]是0
    for(int i=1;i<=n;i++)
        for(int j=0;j<=m;j++)
        {
   
        	//不选第i个物品
            f[i][j]=f[i-1][j];
            if(j>=v[i]){
   
            	//选第i个物品,从选前i-1个物品递推过来
                f[i][j]=max(f[i

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

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

相关文章

如何取消xhr / fetch / axios请求

如何取消xhr请求 setTimeout(() > { xhr.abort() }, 1000)如何取消fetch请求 fetch()请求发送以后&#xff0c;如果中途想要取消&#xff0c;需要使用AbortController对象。 let controller new AbortController(); let signal controller.signal;fetch(url, {signal:…

[激光原理与应用-92]:振镜的光路图原理

目录 一、振镜的光路 二、振镜的工作原理 2.1 概述 2.2 焊接头 2.3 准直聚焦头-直吹头 2.4 准直聚焦头分类——按应用分 2.4.1 准直聚焦头分类——功能分类 2.4.2 准直聚焦头镜片 2.4.3 振镜焊接头 2.4.4 振镜分类&#xff1a; 2.4.5 动态聚焦系统演示&#xff08;素…

vivado Virtex 和 Kintex UltraScale+ 比特流设置

下表所示 Virtex 和 Kintex UltraScale 器件的器件配置设置可搭配 set_property <Setting> <Value> [current_design] Vivado 工具 Tcl 命令一起使用。

Python使用割圆法求π值

三国时期刘徽提出的割圆法有多牛掰&#xff0c;看这个&#xff1a;刘徽割圆术到底做了什么&#xff1f; - 知乎 用Python实现的该算法代码如下&#xff1a; #!/usr/bin/env python """使用割圆法计算π值Usage::$ python calc_circle_pi.py 20 # 参数20是迭代…

ArthasGC日志GCeasy详解

Arthas详解 Arthas是阿里巴巴在2018年9月开源的Java诊断工具,支持JDK6,采用命令行交互模式,可以方便定位和诊断线上程序运行问题.Arthas官方文档十分详细.详见:官方文档 Arthas使用场景 Arthas使用 # github下载arthas wget https://alibaba.github.io/arthas/arthas-boot.j…

uniapp 禁止截屏(应用内,保护隐私)插件 Ba-ScreenShot

禁止截屏&#xff08;应用内&#xff0c;保护隐私&#xff09; Ba-ScreenShot 简介&#xff08;下载地址&#xff09; Ba-ScreenShot 是一款uniapp禁止应用内截屏的插件&#xff0c;保护隐私&#xff0c;支持禁止截屏、放开截屏 截图展示 也可关注博客&#xff0c;实时更新最…

嵌入式学习——C语言基础——day14

1. 共用体 1.1 定义 union 共用名 { 数据类型1 成员变量1; 数据类型2 成员变量2; 数据类型3 成员变量3; .. }; 1.2 共用体和结构体的区别 1. 结构体每个成员变量空间独立 2. 共用体每个成员变量空间共享 1.3 判断内存大小端 1. 内存大端…

Ranni: Taming Text-to-Image Diffusion for Accurate Instruction Following

Ranni: Taming Text-to-Image Diffusion for Accurate Instruction Following abstract 我们引入了一个语义面板作为解码文本到图像的中间件&#xff0c;支持生成器更好地遵循指令 Related work 最近的工作还通过包含额外的条件&#xff08;如补全掩码[15&#xff0c;45]、…

天猫商品搜索API返回值说明:关键字搜索如何精准定位商品,精准定位,一键直达!

通过天猫商品搜索API&#xff0c;关键词搜索不再是难题。精准定位&#xff0c;快速找到您心仪的商品&#xff0c;开启便捷购物新时代。掌握API返回值的奥秘&#xff0c;让您的搜索更智能、更高效&#xff01; 天猫商品搜索API&#xff08;如item_search&#xff09;的返回值设计…

xyctf(write up)

ezhttp 因为是一道http的题&#xff0c;前端代码没有什么有效信息&#xff0c;但提示说密码在某个地方&#xff0c;我们用robots建立一个robots.txt文件来看有哪个文件可以访问 补充知识&#xff1a;http请求中via字段表示从哪个网址的服务器代理而来&#xff0c;user-agent表…

纯血鸿蒙APP实战开发——页面间共享组件实例的案例

介绍 本示例提供组件实例在页面间共享的解决方案&#xff1a;通过Stack容器&#xff0c;下层放地图组件&#xff0c;上层放Navigation组件来管理页面&#xff0c;页面可以共享下层的地图组件&#xff0c;页面中需要显示地图的区域设置为透明&#xff0c;并参考触摸交互控制&am…

git使用注意事项事项

以下操作均在gitee平台上实现 文章目录 1、本地仓库和远程仓库有冲突2、git提交自动忽略某些文件3、git无法push提交到远程仓库 1、本地仓库和远程仓库有冲突 在web端修改了文件内容或者删除了文件&#xff0c;本地仓库需要重新把远程仓库拉取到本地&#xff0c;或者强制提交到…

从零开始学RSA: [WUSTCTF2020]情书等5题

1 [WUSTCTF2020]情书 题目 Premise: Enumerate the alphabet by 0、1、2、..... 、25 Using the RSA system Encryption:0156 0821 1616 0041 0140 2130 1616 0793 Public Key:2537 and 13 Private Key:2537 and 937flag: wctf2020{Decryption}解题 前提&#xff1a;用0、…

GreptimeDB 助力国家电网数字换流站打造稳定高效的时序数据底座

电网体系作为现代社会运行的支柱之一&#xff0c;为各行各业、千家万户提供了电能的基本支持。从家庭到企业&#xff0c;医院到学校&#xff0c;交通到通讯&#xff0c;电力电网的应用贯穿始终。近年来&#xff0c;特高压换流站成为国家电网的重点建设工程&#xff0c;“十四五…

YUM源仓库部署和NFS共享存储服务

一.YUM源仓库部署 1.YUM 概述 &#xff08;1&#xff09;是基于RPM软件包构建的软件更新机制 &#xff08;2&#xff09;可以自动解决依赖关系 &#xff08;3&#xff09;所有软件包有集中的YUM软件仓库提供 2.准备YUM源 &#xff08;1&#xff09;软件仓库的提供方式&…

计算机组成结构—高速缓冲存储器(Cache)

目录 一、Cache的基本工作原理 1.Cache工作原理 2.命中率 3.Cache的基本结构 4.Cache的改进 二、Cache和主存之间的映射方式 1.直接映射 2.全相联映射 3.组相联映射 三、Cache中主存块的替换算法 四、Cache的写策略 概为了解决 CPU 和主存之间速度不匹配的问题&#x…

基于springboot+vue+Mysql的点餐平台网站

开发语言&#xff1a;Java框架&#xff1a;springbootJDK版本&#xff1a;JDK1.8服务器&#xff1a;tomcat7数据库&#xff1a;mysql 5.7&#xff08;一定要5.7版本&#xff09;数据库工具&#xff1a;Navicat11开发软件&#xff1a;eclipse/myeclipse/ideaMaven包&#xff1a;…

redis stream 作为消息队列的最详细的命令说明文档

简介 stream 作为消息队列&#xff0c;支持多次消费&#xff0c;重复消费&#xff0c;ack机制&#xff0c;消息异常处理机制。 涉及到以下几个概念&#xff0c;消息流&#xff0c;消费者组&#xff0c;消费者。 涉及到以下命令 # 添加消息到流中 XADD key [NOMKSTREAM] [&…

Al加码,引爆“躺平式”旅游 | 最新快讯

旅游业正迎来新的技术浪潮。 文&#xff5c;锌刻度&#xff0c;作者&#xff5c;孟会缘&#xff0c;编辑&#xff5c;李季 今年的五一&#xff0c;“微度假”“微旅行”纷纷出圈。 相较于三亚、云南等老牌旅游大热门&#xff0c;人们开始寻找一些不用“人挤人”的小众旅行目的…

谁能取代迈巴赫,征服互联网安全大佬周鸿祎?

‍作者 |老缅 编辑 |德新 4月18日&#xff0c;「周鸿祎卖车」登上了微博热搜。这位360创始人、董事长发微博称&#xff1a;自己做了一个艰难的决定&#xff0c;将把陪伴9年的迈巴赫600给卖掉。 随后&#xff0c;他解释道&#xff1a;「这是因为我需要体验新一代车的感觉。古人…
最新文章