算法 动态规划 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;
}

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

热门文章

暂无图片
编程学习 ·

『杭电1251』统计难题

Problem DescriptionIgnatius最近遇到一个难题,老师交给他很多单词(只有小写字母组成,不会有重复的单词出现),现在老师要他统计出以某个字符串为前缀的单词数量(单词本身也是自己的前缀).Input输入数据的第一部分是一张单词表,每行一个单词,单词的长度不超过10,它们代表的是老师…
暂无图片
编程学习 ·

machine learning基础知识(Leetcode)

机器学习 machine learning是机器通过已知的内容,类似于人类一样进行学习,并对同类型数据进行判断的过程。 例如训练图片模型就是将每个像素点转为0到255之间的值,利用机器发现不同种类的图片之间存在的映射。 有监督与无监督模型监督学习是F(x)= sum 并且sum已知,可以通…
暂无图片
编程学习 ·

后台开发核心技术(11):多线程

背景介绍 进程:以前,进程是最小的执行单位。进程是包含程序指令和相关资源的集合,每个进程和其他进程一起参与调度,竞争CPU、内存等资源。每次进程的切换,都存在着进程资源的保存和恢复动作,这称为上下文切换。 发现问题:比如一个简单的GUI程序,为了有更好的交互性,通…
暂无图片
编程学习 ·

活动目录的备份和恢复

活动目录的备份和恢复AD的备份和恢复AD回收站说明启用回收站功能演示AD回收站AD活动目录的备份和还原AD活动目录的备份安装Windows Server Backup工具添加角色和功能开始之前-安装类型-服务器选择-服务器角色,默认下一步功能确认结果开始备份AD活动目录AD活动目录的恢复重启按…
暂无图片
编程学习 ·

ssm

目录User.javaUserController.javaUserDao.javaUserService.javaIUserService.javaUserMapper.xmlapplicationContext.xmldb.propertiesspring-mvc.xmlapplicationContext.xmlweb.xmlfailure.jspIndex.jspok.jsp pring 1.控制反转-》控制权的转移 2.依赖注入 DI 3.面向切面 aop…
暂无图片
编程学习 ·

XML DOM摘要四(XMLHttpRequest 对象)

什么是 XMLHttpRequest 对象?XMLHttpRequest 对象提供了在网页加载后与服务器进行通信的方法。XMLHttpRequest 对象是开发者的梦想,因为您能够:在不重新加载页面的情况下更新网页在页面已加载后从服务器请求数据在页面已加载后从服务器接收数据在后台向服务器发送数据 所有现…
暂无图片
编程学习 ·

Docker镜像管理透析

欢迎关注【无量测试之道】公众号,回复【领取资源】, Python编程学习资源干货、 Python+Appium框架APP的UI自动化、 Python+Selenium框架Web的UI自动化、 Python+Unittest框架API自动化、资源和代码 免费送啦~ 文章下方有公众号二维码,可直接微信扫一扫关注即可。1、docker,镜…
暂无图片
编程学习 ·

客户端渲染与服务端渲染

本人是前端小白菜,最近在苦学前端,做点自己的学习小总结。欢迎各位大佬纠错。 模版引擎原来一开始是后端使用的,后来才慢慢支持前端,听起来很高大上的模版引擎,什么页面渲染,我不喜欢这么专业的难懂的叫法,所以我要自己亲自总结一下。 服务端渲染模版引擎不关心内容,只…
暂无图片
编程学习 ·

LittleVGL 源码分析--src/lv_misc/lv_log.h

这是log配置信息:/*================* Log settings 日志设置*===============*//*1: Enable the log module 启用日志模块 */ #define LV_USE_LOG 1 #if LV_USE_LOG /* How important log should be added:* LV_LOG_LEVEL_TRACE A lot of logs to give detailed…
暂无图片
编程学习 ·

Linux下redis的安装及用法

Linux下redis的安装及用法 下面介绍在Linux环境下,Redis的安装与部署 1、在安装redis之前先安装C++编译环境,查看目前服务器上gcc的版本:gcc -v, 如果Linux系统没有安装gcc编译器,会提示“Command not found”;如果提示命令找不到,则表明没有安装; 或者更新版本,不然后…
暂无图片
编程学习 ·

归并排序

给定你一个长度为n的整数数列。 请你使用归并排序对这个数列按照从小到大进行排序。 并将排好序的数列按顺序输出。 输入格式 输入共两行,第一行包含整数 n。 第二行包含 n 个整数(所有整数均在1~109范围内),表示整个数列。 输出格式 输出共一行,包含 n 个整数,表示排好序…
暂无图片
编程学习 ·

计算机专业大学生的随感

我想去聚会,想和朋友一起喝酒,但是仔细一想,自己好像没有可以去的聚会,也没有可以陪着自己喝酒的朋友。 懒得在社交上花费时间和精力,那么需要朋友的时候,就只能对着屏幕空感叹。 那几分GPA虽然重要,但真的不至于占用自己那么多时间
暂无图片
编程学习 ·

Postman调用 .net 的webservice

1、使用post方式调用,url以 asmx 止。2、设置header,content-type text/xml;charset=utf-8。3、body里选择 raw,参数模板如下:<soap:Envelope xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xmlns:xsd="http://www.w3.org/2001/XMLSch…
暂无图片
编程学习 ·

GIS开发:如何开发一个MBTiles Server

MBTiles是一个存储地图切片的数据库,以SQLite数据为基础,将地图切片按照缩放级别、横行和纵行的顺序,存储在其中。 常见的Geoserver可以加载插件,对MBTiles进行发布,github上也有开源的MBTiles Server,也可以进行MBTiles发布。 在只需要地图的切片情况下,如何进行一个MB…
暂无图片
编程学习 ·

驾考知识自查

驾考知识自查1事故的种类没有车辆追尾路段,只有事故多发路段2驾驶证 行驶证的换领驾驶证为核发地 行驶证为登记地3山坡挂挡问题p=fv 机动车功率一定 抵挡获得更大的牵引力,但不可以松开加速踏板,松开会导致遛坡4违规处罚问题饮酒后驾驶机动车的,处暂扣六个月机动车驾驶证,…
暂无图片
编程学习 ·

spring 使用事件驱动

概述: 一、三要素 1、监听器:Listener 2、事件源:event 3、事件的发布者:Publisher 二、实现方式 1、事件源:Event设计 // 重点是继承 ApplicationEvent public class MyEvent extends ApplicationEvent {private static final long serialVersionUID = -6921924726678224…
暂无图片
编程学习 ·

bootAnimation有卡顿

因为我是Mac操作的文件,里面包含了隐藏文件 .DS_Store 文件 需要把 .DS_Store 删除 解决方案1.删除所有隐藏.DS_store文件,打开命令行窗口sudo find / -name ".DS_Store" -depth -exec rm {} \; 2.设置不再产生选项, 执行如下命令defaults write com.apple.desktop…
暂无图片
编程学习 ·

自动翻译器2

自动翻译器的qt部分接下来我们要实现qt窗口部分,这里遇到一个很尴尬的事情,qt for python的开发环境要求按照python,但我安装的是Anaconda,使用Jupyter开发,安完了PySide2,Qt找不到这个模块,用Jupyter呢,又提示找不到qt.qpa.plugin,打开环境变量查看os.environ, QT_Q…