算法 动态规划 0-1背包

动态规划2

给定n种物品和1个背包,物品i的重量是wi,其价值为vi,背包的容量为C。要求选择装入背包的物品,使得装入背包中物品的总价值最大。

例如5个物品,wi[] = { 2,4,6,3,8},vi[]={6,6,3,7,5},背包的容量为10

#include<iostream>
using namespace std;
#include<iomanip>
#define N 5  //物品个数
#define C 10  //物品容量
int wi[] = {2,4,6,3,8};
int vi[] = {6,6,3,7,5};
int value[N+1][C+1] = {0};
void table() {
 int i,j;
 //i表示背包现有的物品,
 //j表示背包现容量
 for(i=1;i<=N;i++) {
  for(j=1;j<=C;j++) {
   if(j<wi[i-1]) //放不下
    value[i][j] = value[i-1][j];
   else {//放得下
    int t1 = value[i-1][j];//不放
    int t2 = value[i-1][j-wi[i-1]] + vi[i-1];//放
    value[i][j] = t1 > t2 ? t1 : t2;//最大价值
   }
  }
 }
}
int S[N] = {0};
void getSelected(int n,int c) {//倒推被选中的物品
 if(n<=0||c<=0)//出口
  return;
 if(value[n][c]>value[n-1][c]) {
  S[n-1] = 1;//选中
  c -= wi[n-1];//容量改变
 }
 getSelected(--n,c);//前一个物品
}
int getValue(int n,int c) {
 return value[n][c];
}

int main() {
 cout<<"价值表如下:"<<endl;
 table();
 for(int i=0;i<=N;i++) {
  for(int j=0;j<=C;j++)
   cout<<setw(4)<<value[i][j]<<" ";
  cout<<endl;
 }
 cout<<"该题的最大价值:"<<endl;
 cout<<getValue(5,10)<<endl;
 getSelected(5,10);
 for(int i=0;i<N;i++)//选择的物品情况
  cout<<S[i]<<" ";
 getchar();
 return 0;
}

运行结果如下:
动态规划结果图

热门文章

暂无图片
编程学习 ·

使用pip离线安装python扩展包依赖模块

简答来说就是从一台有网的主机下载好,放到离线主机上,用pip实现1.查看安装了哪些pip3 freeze网上一般都是pip3 freeze >requirements.txt 这就是查看安装了那些,然后存到文件里面2.就是把安装好的打包了,上面那个文件存的就是要打包的,我们完全可以直接,在里面写好想…
暂无图片
编程学习 ·

C++核心准则ES.40:避免复杂的表达式

ES.40: Avoid complicated expressionsES.40:避免复杂的表达式Reason(原因)Complicated expressions are error-prone.复杂的表达式容易引发错误。Example(示例)// bad: assignment hidden in subexpression while ((c = getc()) != -1)// bad: two non-local variables as…
暂无图片
编程学习 ·

分布式数据存储系统之三要素

什么是分布式数据存储系统? 分布式存储系统的核心逻辑,就是将用户需要存储的数据根据某种规则存储到不同的机器上,当用户想要获取指定数据时,再按照规则到存储数据的机器里获取。 如下图所示,当用户(即应用程序)想要访问数据 D,分布式操作引擎通过一些映射方式,比如 H…
暂无图片
编程学习 ·

HBase环境搭建

前提 Hadoop环境 Zookeeper集群上传解压HBase压缩包 #解压hbase tar -zxvf hbase-0.98.12.1-hadoop2-bin.tar.gz#重命名 mv hbase-0.98.12.1-hadoop2 hbase-0.98#移动至/opt/spurce/目录下 mv hbase-0.98 /opt/source/修改配置文件 配置RegionServer,把集群节点添加到regionse…
暂无图片
编程学习 ·

双亲委派模型

原理 双亲委派模式是在Java 1.2后引入的,其工作原理的是,如果一个类加载器收到了类加载请求,它并不会自己先去加载,而是把这个请求委托给父类的加载器去执行,如果父类加载器还存在其父类加载器,则进一步向上委托,依次递归,请求最终将到达顶层的启动类加载器,如果父类加…
暂无图片
中恒嘉业 ·

关于主从复制的超详细解析(全)

目录前言1. 主从复制1.1 方式2. Mysql的主从复制2.1 一主一从2.1.1 window和linux通讯2.1.2 linux和linux的通讯2.2 双主双从3. Redis的主从复制3.1 哨兵模式3.2 java代码结合前言 主要介绍mysql的主从复制以及redis的主从复制 能由浅入深的明白原理以及如何操作 再者&#xf…
暂无图片
郑州普通话 ·

ffmpeg合并音视频,flutter游戏源代码

JetPack里的组件上图就是JetPack中包含的组件列表,每个组件都是相对独立的,可以被单独使用和构建。其中像被介绍的最多,也是最常被使用的LiveData, ViewModel, Room, Navigation, WorkManager之类的都发布了正式版,而CameraX, Compose之类的还处在Alpha版本,未正式发布,官…
暂无图片
郑州普通话 ·

apm性能监控系统,kotlindata类

进阶之路 为何会想起写这么一篇文章呢,一方面很多程序员对于技术精进仍然十分困惑,不知道该如何学习进阶,以至于提前陷入中年危机的困惑之中,作为一名Android开发近十年的老码农或许可以分享一些自己的心得体会,刚好这几天工作需要,组内想规划 Android 技术路线,简单来说…
暂无图片
代理记账 ·

在web应用中发送和接收Jakarta消息

Running the websimplemessage Example To Package and Deploy websimplemessage Using Maven _1、Make sure that GlassFish Server has been started (see Starting and Stopping GlassFish Server). _2、In a terminal window, go to: tut-install/examples/jms/websimp…
暂无图片
cgfy ·

C++学习日记2——函数、封装、对象特性

一、函数 1.1 函数默认参数 1.1.1 简介 在C中&#xff0c;函数的形参列表中的形参是可以有默认值的 1.1.2 语法 返回值类型 函数名 (参数 默认值) {} 1.1.3 代码 #include <iostream> using namespace std;// 函数的默认参数 int func(int a, int b 20, int c 30…
暂无图片
coreui ·

视频水印怎么去除?超简单 千万不要错过

小编在知乎看到很多大佬分享的视频去水印的方法&#xff0c;但是感觉都有点太复杂了&#xff0c;今天就来分享一下小编自己私藏的几个针对于视频去水印的软件和网站~建议大家收藏哦~ 1、爱给网-视频去水印小工具&#xff08;免费 在线&#xff09; 推荐点 1、在线操作&#…
暂无图片
coreui ·

Mac 安装 tomcat10

Mac 安装 tomcat10 1、下载tomcat tomcat官网&#xff1a;https://tomcat.apache.org/ 点击我下载的tomcat10&#xff1a; 2、下载解压,给bin下的*.sh文件添加可执行权限 3、修改webapps下的ROOT中的index文件查看效果
暂无图片
未来博客 ·

视频水印怎么去除?超简单 千万不要错过

小编在知乎看到很多大佬分享的视频去水印的方法&#xff0c;但是感觉都有点太复杂了&#xff0c;今天就来分享一下小编自己私藏的几个针对于视频去水印的软件和网站~建议大家收藏哦~ 1、爱给网-视频去水印小工具&#xff08;免费 在线&#xff09; 推荐点 1、在线操作&#…
暂无图片
未来博客 ·

Mac 安装 tomcat10

Mac 安装 tomcat10 1、下载tomcat tomcat官网&#xff1a;https://tomcat.apache.org/ 点击我下载的tomcat10&#xff1a; 2、下载解压,给bin下的*.sh文件添加可执行权限 3、修改webapps下的ROOT中的index文件查看效果
暂无图片
建站日记 ·

惠州实验室建设选址、勘察事项

惠州实验室建设选址、勘察事项&#xff0c;SICOLAB技术员带您从实验室建设启动前思考问题考虑如下&#xff1a;一、不同实验室建设选址要求 1.化学实验室 &#xff08;1&#xff09;清洁安静环境 &#xff08;2&#xff09;远离住宅、生活区 &#xff08;3&#xff09;锅炉房与…
暂无图片
建站日记 ·

NLP聊天机器人原理(seq2seq模型)

一、seq2seq模型 1.概念 seq2seq是一个Encoder-Decoder结构的网络&#xff0c;它的输入是一个序列&#xff0c;输出也是一个序列。Encoder中将一个可变长度的信号序列变为固定长度的向量表达&#xff0c;Decoder将这个固定长度的向量变成可变长度的目标的信号序列。这个结构最…
暂无图片
mfbz ·

惠州实验室建设选址、勘察事项

惠州实验室建设选址、勘察事项&#xff0c;SICOLAB技术员带您从实验室建设启动前思考问题考虑如下&#xff1a;一、不同实验室建设选址要求 1.化学实验室 &#xff08;1&#xff09;清洁安静环境 &#xff08;2&#xff09;远离住宅、生活区 &#xff08;3&#xff09;锅炉房与…
暂无图片
mfbz ·

全渠道会员通-天猫会员通3: 会员运营内容准备

在天猫会员通技术对接开发过程中&#xff0c;为了通知存量会员的通知工作&#xff0c;发挥会员通的优势&#xff0c;品牌需要做好以下事宜&#xff1a; 会员体系暂停公告&#xff1a;因会员通技术升级期间&#xff0c;会员服务将被暂停&#xff0c;店铺tab中会员入口将被下线&…
暂无图片
珊珊日记 ·

C# 执行Javascript脚本

c#教程https://www.xin3721.com/eschool/CSharpxin3721/ 前一阵子使用C#编写SCXML状态机&#xff0c;需要解析EMCScript表达式&#xff0c;使用了Jint库&#xff08;https://github.com/sebastienros/jint/)&#xff0c;当时感觉与C#之间的数据转换不是很方便。这两天有时间又关…
暂无图片
珊珊日记 ·

第九届“图灵杯”NEUQ-ACM程序设计竞赛个人赛

A.大学期末现状 题目描述 作为一名大学生的你&#xff0c;现在又到了期末查成绩的时候&#xff0c;当你的成绩大于等于60时请输出“jige,haoye!”,否则输出"laoshi,caicai,laolao"。 输入描述: 一行&#xff0c;一个整数x代表你的成绩&#xff08;0<x<100&a…