(C++)背包问题

#include<iostream>
using namespace std; 

int main(){
//问题: 
//有编号分别为1,2,3,4的四件物品,它们的
//重量分别是      3, 7, 2, 1
//它们的价值分别是9,14,10, 4
//每件物品数量只有一个,现在给你个承重为10的背包,
//如何让背包里装入的物品具有最大的价值总和? 



//一个存放物品及对应重量和价值的二维数组
//默认生成一个大小为0,价值为0的物品 (但是可以不用赋值,数组默认赋值) 
//这个大小和价值为0的物品在后面有大用 
int goods[5][2];



//第一个序号——第几个物品 
//第二个序号——0是重量 1是价值 
goods[1][0]=3;  
goods[1][1]=9; 
goods[2][0]=7;
goods[2][1]=14; 
goods[3][0]=2;  
goods[3][1]=10; 
goods[4][0]=1;
goods[4][1]=4;



//创建一个大数组,存放后面的数据 
int arr[5][11];
//数组——列长为:5 行宽为:11 
//0~10对应当前背包大小
//0~4 对应当前物品序号
//效果如下: 
//\ 0 1 2 3 4 5 6 7 8 9 10
//0
//1
//2 
//3
//4



//现在给行列序号为0的先赋值为0
//(也可以不做这步,这里只是方便理解) 
for(int i=0;i<11;i++){
	arr[0][i]=0;
	arr[i][0]=0;
} 
//效果如下:
//\ 0 1 2 3 4 5 6 7 8 9 10
//0 0 0 0 0 0 0 0 0 0 0 0 
//1 0
//2 0
//3 0
//4 0


//从左到右从,从上到下,一排一排扫描判断 

//下面是对if判断语句的解释: 
//if(当前背包容量j < 当前待加入物品重量good[i][0]){
//则当前位置对应最大价值arr[i][j] = 它头顶位置对应的最大价值arr[i-1][j]}
// if(当前背包容量j >= 当前待加入物品重量good[i][0]){
// { 当前位置对应最大价值 = (判断下面1,2哪个更大); 
//1.它头顶位置对应的最大价值arr[i-1][j] , 
//2.(比它头上位置"对应的背包容量"arr[i-1][j] 小 当前位置对应物品重量goods[i][0] 的位置的价值 加上当前物品价值goods[i][1])
//(arr[i-1][j-goods[i][0]]+goods[i][1])
for(int i=1;i<=4;i++){
	for(int j=1;j<=10;j++){
		if(j<goods[i][0]){
			arr[i][j]=arr[i-1][j];
		}
		if(j>=goods[i][0]){
			if(arr[i-1][j]>(arr[i-1][j-goods[i][0]]+goods[i][1])){
				arr[i][j]=arr[i-1][j];
			}else{
				arr[i][j]=(arr[i-1][j-goods[i][0]]+goods[i][1]);
			}
		}
	}
} 



for(int i=0;i<5;i++){
	for(int j=0;j<11;j++){
		cout<<arr[i][j]<<"\t";
	}
	cout<<endl;
}
//最后: 
//0       0       0       0       0       0       0       0       0       0       0
//0       0       0       9       9       9       9       9       9       9       9
//0       0       0       9       9       9       9       14      14      14      23
//0       0       10      10      10      19      19      19      19      24      24
//0       4       10      14      14      19      23      23      23      24      28

//从上面可以看出 当背包容量大小为10的时候,最大价值为28
}

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

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

相关文章

PWM实验

PWM相关概念 PWM:脉冲宽度调制定时器 脉冲&#xff1a;方波信号&#xff0c;高低电平变化产生方波 周期&#xff1a;高低电平变化所需要时间 频率&#xff1a;1s钟可以产生方波个数 占空比&#xff1a;在一个方波内&#xff0c;高电平占用的百分比 宽度调制&#xff1a;占…

飞鼠异地组网工具实战之访问k8s集群内部服务

飞鼠异地组网工具实战之访问k8s集群内部服务 一、飞鼠异地组网工具介绍1.1 飞鼠工具简介1.2 飞鼠工具官网 二、本次实践介绍2.1 本次实践场景描述2.2 本次实践前提2.3 本次实践环境规划 三、检查本地k8s集群环境3.1 检查k8s各节点状态3.2 检查k8s版本3.3 检查k8s系统pod状态 四…

RVC从入门到......

RVC变声器官方教程&#xff1a;10分钟克隆你的声音&#xff01;一键训练&#xff0c;低配显卡用户福音&#xff01;_哔哩哔哩_bilibili配音&#xff1a;AI逍遥散人&#xff08;已授权&#xff09;关注UP主并私信"RVC"&#xff08;三个字母&#xff09;自动获取一键训…

PL/SQL编程

一、Oracle常用函数 concat&#xff1a;用于连接两个字符串。 CONCAT(Oraok, .com) -- Result: Oraok.com ceil&#xff1a;小数点向上取整。 secect ceil(7.3) from dual --Result: 8 dual表是oracle系统为计算设计的一张临时表 select sysdate as 系统日期 from dual…

基于寄生捕食算法优化概率神经网络PNN的分类预测 - 附代码

基于寄生捕食算法优化概率神经网络PNN的分类预测 - 附代码 文章目录 基于寄生捕食算法优化概率神经网络PNN的分类预测 - 附代码1.PNN网络概述2.变压器故障诊街系统相关背景2.1 模型建立 3.基于寄生捕食优化的PNN网络5.测试结果6.参考文献7.Matlab代码 摘要&#xff1a;针对PNN神…

我的创作纪念日——365天

机缘 最开始我写博客没有什么特别的原因&#xff0c;主要是因为以下几点&#xff1a; 练习自己的语言组织能力 记录自己学习生活中学到的知识 主要还是想找一个好的保存 Markdown 笔记的平台。 最终我选择了 CSDN&#xff0c;一来是因为 CSDN 对 Markdown 语法的支持较为全面…

NSSCTF第13页(2)

[HNCTF 2022 Week1]Challenge__rce 提示?hint 访问看到了源码 <?php error_reporting(0); if (isset($_GET[hint])) { highlight_file(__FILE__); } if (isset($_POST[rce])) { $rce $_POST[rce]; if (strlen($rce) < 120) { if (is_string($rce…

图片降噪软件 Topaz DeNoise AI mac中文版功能

Topaz DeNoise AI for Mac是一款专业的Mac图片降噪软件。如果你有噪点的相片&#xff0c;可以通过AI智能的方式来处理掉噪点&#xff0c;让照片的噪点降到最 低。有了Topaz DeNoise AI mac版处理图片更方便&#xff0c;更简单。 Topaz DeNoise AI mac软件功能 无任何预约即可在…

基于阿基米德优化算法优化概率神经网络PNN的分类预测 - 附代码

基于阿基米德优化算法优化概率神经网络PNN的分类预测 - 附代码 文章目录 基于阿基米德优化算法优化概率神经网络PNN的分类预测 - 附代码1.PNN网络概述2.变压器故障诊街系统相关背景2.1 模型建立 3.基于阿基米德优化优化的PNN网络5.测试结果6.参考文献7.Matlab代码 摘要&#xf…

IntelliJ IDEA 2023 v2023.2.5

IntelliJ IDEA 2023是一款功能强大的集成开发环境&#xff08;IDE&#xff09;&#xff0c;为开发人员提供了许多特色功能&#xff0c;以下是其特色介绍&#xff1a; 新增语言支持&#xff1a;IntelliJ IDEA 2023新增对多种编程语言的支持&#xff0c;包括Kotlin、TypeScript、…

Windows网络「SSL错误问题」及解决方案

文章目录 问题方案 问题 当我们使用了神秘力量加持网络后&#xff0c;可能会和国内的镜像源网站的之间发生冲突&#xff0c;典型的有 Python 从网络中安装包&#xff0c;如执行 pip install pingouin 时&#xff0c;受网络影响导致无法完成安装的情况&#xff1a; pip config…

【飞控调试】DJIF450机架+Pixhawk6c mini+v1.13.3固件+好盈Platinium 40A电调无人机调试

1 背景 由于使用了一种新的航电设备组合&#xff0c;在调试无人机起飞的时候遇到了之前没有遇到的问题。之前用的飞控&#xff08;Pixhawk 6c&#xff09;和电调&#xff08;Hobbywing X-Rotor 40A&#xff09;&#xff0c;在QGC里按默认参数配置来基本就能平稳飞行&#xff0…

Nginx的核心配置文件

Nginx的核心配置文件 学习Nginx首先需要对它的核心配置文件有一定的认识&#xff0c;这个文件位于Nginx的安装目录/usr/local/nginx/conf目录下&#xff0c;名字为nginx.conf 详细配置&#xff0c;可以参考resources目录下的<<nginx配置中文详解.conf>> Nginx的核…

JavaScript实现飞机发射子弹详解(内含源码)

JavaScript实现飞机发射子弹 前言实现过程源码展示源码讲解HTML结构CSS结构js结构 前言 文本主要讲解如何利用JavaScript实现飞机发射子弹&#xff0c;实现过程以及源码讲解。实现效果图如下&#xff1a; 实现过程 首先&#xff0c;找到飞机和子弹的UI图&#xff0c;gif图最…

局域网内Ubuntu上搭建Git服务器

1.在局域网内选定一台Ubuntu电脑作为Git服务端&#xff1a; (1).新建用户如为fbc&#xff0c;执行如下命令&#xff1a;需设置密码&#xff0c;此为fbc sudo adduser fbc (2).切换到fbc用户&#xff1a;需密码&#xff0c;此前设置为fbc su fbc (3).建一个空目录作为仓…

Vue3-provide 和 inject 跨组件传递数据

Vue3-provide 和 inject 跨组件传递数据 功能&#xff1a;将数据从App组件跨过一个组件传递到B组件中provide&#xff1a;提供数据inject&#xff1a;接收数据 // App.vue <template><h2>我是App组件&#xff08;{{num}}&#xff09;</h2><A></A&g…

关于SPJ表的数据库作业

打字不易&#xff0c;且复制且珍惜 建表 use 库名;create table S( --供应商 SNO char(6) not null, SNAME char(10) not null, STATUS INT, CITY char(10), primary key(SNO));create table P( --零件 PNO char(6) not null, PNAME char(12)not null, COLOR char(4), WEIGHT…

如何在el-tree懒加载并且包含下级的情况下进行数据回显-02

上一篇文章如何在el-tree懒加载并且包含下级的情况下进行数据回显-01对于el-tree懒加载&#xff0c;包含下级的情况下&#xff0c;对于回显提出两种方案&#xff0c;第一种方案有一些难题无法解决&#xff0c;我们重点来说说第二种方案。 第二种方案是使用这个变量对其是否全选…

【C++】:模板的使用

目录 1、泛型编程 2、函数模板 2.1、函数模板概念 2.2、函数模板格式 2.3、函数模板的原理 2.4、函数模板的实例化 2.6、模板参数的匹配原则 3、类模板 3.1、 类模板的定义格式 3.2、 类模板的实例化 4、非类型模板参数 5、模板的特化 5.1、函数模板特化 5.2、类模…

达标进度条

1.效果 1. 2.代码与使用 1.自定义组合控件 kotlin import android.annotation.SuppressLint import android.content.Context import android.graphics.drawable.Drawable import android.util.AttributeSet import android.view.Gravity import android.view.LayoutInflat…