九大背包问题专题--完全背包问题(详解,最优解)_完全背包问题详解-程序员宅基地

技术标签: c++  背包问题  

2.完全背包问题

和01背包问题的区别:
01背包问题:1件物品只能选或者不选

完全背包问题:1件物品可以重复选多次,只要不超过总体积

题目:
问题:
有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

输出样例
10

分析思路:

f[i]:表示总体积是i的情况下,最大价值是多少

f[0…m]枚举,m表示背包容量
result=max{f[0…m]}

01背包从大到小枚举->保证每个物品只用1次

从前往后考虑
for(int i=0;i<n;i++){
    
    for(int j=m,j>=v[i];j--)
       f[j]=max(f[j],f[j-v[i]]+w[i])
原因:保证状态转移时,算f[j]时,算的是f[i][j](第i个物品的j),保证转移时,用的是f[i-1][j]
f[j]=max(f[j],f[i-1][j-v[i]]+w[i]);
而不是 f[j]=max(f[j,]f[i][j-v[i]]+w[i])
从大到小枚举,v[i]>0,[j-v[i]]一定没有被算过,则它一定是f[i-1]的状态。

完全背包从小到大枚举->保证在背包容量允许的条件下,每个物品可重复多次使用


现在枚举第i个物品,体积从大到小枚举
 for(int j=m,j>=v[i];j--)
   for(int k=0;k*v[i]<=j;k++)  //选的物品数
      f[j]=max(f[j],f[j-k*v[i]]+k*w[i])  //一个物品重复选多次,直到装不下,一定不包含当前的第i个物品
算f[j]时,用来转移的状态一定是f[i-1]的

算f[j]时,所有比j小的f[j]都没有被算过,上面所有的f[j-k*v[i]都没算过,都不包含第i个物品

枚举选k个,对不同的k,更新刚才的状态,体积就是j-k*v[i]],价值就是k*w[i]

从小到大枚举,在算f[j]时,用j-v[i]这个状态,j-v[i]这个状态是被算过的,
因为从小到大枚举,所以算f[j]时,比j小的都已经算过了,j-v[i]也在里面,所以j-v[i]这个状态也被算过了

f[j-v[i]]表示考虑前i个物品,包括第i个物品的情况下,体积是j-v[i]时,最大价值是多少,可能已包含若干的当前第i个的物品。

综上,从小到大更新状态,f[j-v[i]]包含第i个物品,证明从小到大枚举能枚举到最优解.

证明:数学归纳法(迭代,递推关系)

1.假设前i-1个物品考虑完之后,所有的f[j]都是符合的,所有f[j]表示体积是j的情况下,它的最大价值就是f[j]
初始化:f[0][0]正确

2.考虑完第i个物品后,所有f[j]也是符合的

对某一个j而言,把j确定,最优解里面包含k个v[i],第i个物品

从小到大枚举,一定可以枚举到f[j-k*v[i]]状态,算此状态时,
用f[j-k*v[i]-v[i]]+w[i]更新状态(此最优解不包含v[i]),

反之f[j-k*v[i]]不包含,所以不会更新,取完max后一定是原来的数
f[j-k*v[i]]此状态已算完

接着算(k-1)*v[i]状态:f[j-(k-1)*v[i]]会用f[j-v[i]]+w[i])更新它,更新之后变为:f[j-k*v[i]-v[i]]+w[i]

综上:f[j-(k-1)*v[i]]这个状态会用f[j-k*v[i]](一个v[i]都不包含)这个状态更新;枚举完一个之后就会包含一个v[i],
依次类推:算f[j]时,用f[j-v[i]]+w[i])(此状态一定计算过只包含k-1个物品这个状态)更新,所以说f[j]这个物品枚举了包含k个v[i]

如果最后结果中包含k个v[i],那么f[j]就一定枚举到过这种状态
所以f[j]就一定会枚举到最优解

举例:
1、前1个物品中:f[1]=2,f[2]=4,f[3]=6,f[4]=8,f[5]=10,显然f[j]都是正确的。
2、假设在前i-1个物品中,f[j]都是正确的。
3、在前i个物品中,对于某个j而言,如果最优解包含k个v[i],则一定会枚举到f[j-kv[i]],f[j-kv[i]]是如何得到的呢?
f[j-kv[i]=max{f[j-kv[i]],f[j-kv[i]-v[i]]+w[i]} (由于j正序,f[j-kv[i]]为前i-1个物品的值,f[j-k*v[i]-v[i]]为前i个物品的值).
最后会传递到max{f[v[i]],f[0]+w[i]}处。

因为f[v[i]]一定正确(2中已假设前i-1个物品中的f[j]全都正确),f[0]一定正确=0,w[i]一定正确,所max{f[v[i]],f[0]+w[i]}
一定正确=>f[j-k*v[i]]一定正确=>f[j]一定正确.

时间复杂度:1000000
代码:

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;

const int N=1010;
int n,m; 
int f[N];
int main(){
    
	cin>>n>>m;
	for(int i=0;i<n;i++){
      //从0开始枚举 
		int v,w;
		cin>>v>>w;
		for(int j=v;j<=m;j++) //小到大枚举体积,<v的不枚举 
		  f[j]=max(f[j],f[j-v]+w);
	} 
	/*初始化的时候把所有的 f[i]都初始化为0 
	/f[m] 表示体积 小于等于m的情况下 ,所有方法里面 
	/转移的时候不一定是从f[0]转移过来的,可以从任意一个状态转移 
	/当用不完整个背包的容量的时候 ,假设剩k容量就可以从k转移 
	/则一定可以枚举到 最优解一样的选法 ,因为体积变成了一样的 
	/假设最优解用了m-k的体积,f[m]就一定可以从k开始枚举 ,也只用了 m-k的体积
	 也会枚举到最优解 ,所以f[m]表示的就是体积小于等于 m的情况下的最优解 */ 
	cout<<f[m]<<endl;  //最大价值(不需要枚举从0到m) 
	return 0;
}

在这里插入图片描述
若题目问体积恰好为m的情况下,最大价值为多少?
除f[0]=0
在初始化时所有f[i]初始化为负无穷

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/gl620321/article/details/105799605

智能推荐

Win10 利用 IIS(Internet Information Services)搭建FTP服务器_internet information server运行路径-程序员宅基地

文章浏览阅读1.1k次。这里使用的是系统自带的**IIS(Internet Information Services)**搭建FTP服务器。一、启动IIS以及FTP相关的服务打开控制面板–>程序和功能–>启动或关闭Windows功能运行 control 可以打开控制面板。主要就是把FTP服务器、IIS管理控制台勾起来,其他的也可以根据需要勾选。二、搭建FTP服务器1、打开IIS路径:C:\Windows\system32\inetsrv\InetMgr.exe也可以通过搜索框搜索到程序2、_internet information server运行路径

olimx_jtag连接异常问题:Missing mandatory configuration. Fill-in the ‘Config options:‘ field in the Debugge_missing mandatory configuration. fill-in the 'conf-程序员宅基地

文章浏览阅读2.1k次。使用olimx-jtag仿真时出现错误:在Config option 添加 .f “board/olimx_jtag.cfg”,点击Debug还是报logOpen On-Chip Debugger 0.10.0+dev (SiFive OpenOCD 0.10.0-2019.08.2)Licensed under GNU GPL v2For bug reports: https://github.com/sifive/freedom-tools/issues..._missing mandatory configuration. fill-in the 'config options:' field in the

工作一年心路历程及个人感悟_心路历程感悟-程序员宅基地

文章浏览阅读2k次。在大三实习了一个月,毕业后不知不觉中工作了又一年了。2020年是一个混乱的年度,本来这时的我该去公司实习,却只能由于疫情待在家中,并忍受父母白眼,一度心情憋闷和抑郁。那时候没事做,学习也没方向,便玩了一波又一波的游戏,看了一波又一波动漫,空洞骑士、蔚蓝、群星、街霸等玩了不少,哈哈。之后又是忙毕业设计,疫情松懈了又钓钓鱼,出去乱窜,觉得自己应该像流浪汉一样四海为家,到处乱跑更合心意。 说回工作,我大学签的一家国企控股公司,确确实实感受到了国企风格。国企工作..._心路历程感悟

uni-app app定位当前地理位置_uniapp地图显示设备位置-程序员宅基地

文章浏览阅读1.7k次。首先申请地图的key,然后在manifest.json文件中配置,如下图下面直接上代码getLocation: function() { let that = this uni.getLocation({ type: 'wgs84', geocode: true, success: function(res) { var point = new plus.maps.Point(res.longitude, res.latitude); plus.maps.Map.reverseG_uniapp地图显示设备位置

深度学习:Self-Attention与Multi-heads Attention详解_multi-head self-attention-程序员宅基地

文章浏览阅读796次。分为dot product 和 与 additive ,前者就是计算出q k后,做点乘(对应元素相乘在相加),然后得到q对所有k的相关性,然后经过softmax处理得到attention score,在大部分情况下我们都采用这种方法,后者则是做加法然后经过tanh激活得到。然后通过fx,把 x Embedding成低维向量a1,a2,让后对a1,a2分别通过全连接层(对应的权重矩阵w)得到对应的q(query),k(key),v(value)。(实际是不同的head的所对应的q权重矩阵不同。_multi-head self-attention

按键控制8*8led点阵C语言程序,单片机按键控制8X8LED点阵屏显示图形 程序的几个问题...-程序员宅基地

文章浏览阅读2.8k次。/* 名称:按键控制8X8LED点阵屏显示图形说明:每次按下K1时,会使8X8LED点阵屏循环显示不同图形。本例同时使用外部中断和定时中断。*/#include#include#define uchar unsigned char#define uint unsigned int//待显示图形编码uchar code M[][8]={{0x00,0x7e,0x7e,0x7e,0x7e..._多个按键按键控制点阵屏显示

随便推点

vuecli2.x版本构建的项目如何配置环境变量_vue-cli2搭建的项目如何判断正式服, 如何设置node_env-程序员宅基地

文章浏览阅读1k次,点赞3次,收藏4次。vuecli2.x构建的项目目录和vuecli3.x/4.x是不同的在vuecli2.x版本构建的项目根目录中有build和config文件夹如下:我们接下来只讲vuecli2.x是如何配置环境变量的一般会划分哪些环境呢?开发环境development,测试环境test,正式环境production为什么要划分?开发的时候我们访问接口地址都是访问他们的ip地址;开发完了项目打包到放到测试服务器,你的接口地址要变成测试地址;上线了接口地址又要改成正式地址;总不能每次手动切换把,而且不仅仅是接口地_vue-cli2搭建的项目如何判断正式服, 如何设置node_env

解决ViewPager中嵌套ViewPager的滑动分发问题_viewpage套viewpager套viewpager-程序员宅基地

文章浏览阅读2.6k次。本文主要解决ViewPager中嵌套ViewPager的滑动分发问题,自定义ViewPager,即BannerViewPager。阻止子ViewPager中滑动事件不再分发给父ViewPager滑动。_viewpage套viewpager套viewpager

C#餐厅管理系统6--呼叫管理员!_c#呼叫网管-程序员宅基地

文章浏览阅读5.4k次。C#餐厅管理系统6--呼叫管理员! 地址:点击打开链接C#餐厅管理系统5--餐桌和职员 地址:点击打开链接C#餐厅管理系统4--增删改查! 地址:点击打开链接C#餐厅管理系统3--MAIN窗口 地址:点击打开链接C#餐厅管理系统2--数据连接及登录 地址:点击打开链接C#餐厅管理系统1_c#呼叫网管

Unity3D .asset资源文件_u3d的.asset-程序员宅基地

文章浏览阅读1.5w次,点赞5次,收藏14次。在游戏开发中,经常会用到一些配置文件保存一些数据,然后项目运行中读取这些配置文件中的数据在游戏中使用。如:配置血条:根据角色类型(人物、动物、怪物等)配置不同的血条,包括血条大小,血条名或血条预设,血条颜色等一些简单数据。如:配置子弹:子弹类型(真子弹、假子弹、追踪子弹等),子弹速度,伤害数值,子弹关联的特效等。诸如此类的配置很多种,可创建一个可序列化的类存储数据,或者创建 XML 、JSON 文..._u3d的.asset

qtcreator qmake subdirs多工程编译依赖的坑-程序员宅基地

文章浏览阅读891次。注意,以下写法是错的:TEMPLATE=subdirsSUBDIRS=\src/app\#relativepathssrc/lib\src/lib2app.depends=liblib2虽然qmake可以解析出子工程叫lib 和lib2,但是就是无法depends!要用工程名+子目录 .subdir 架构才能识别:qmake拷贝文件,以及QMAKE_COPY等命令解释,q..._qmake subdir

Windows7 64位+Cuda6.5+vs2012 的caffe配置历程_无法打开包括文件“gtest/gtest.h” :no such file or directory-程序员宅基地

文章浏览阅读2.3k次。Cuda6.5安装备注:已经装好cuda的请略过,往下看。 记得没有VS2012的一定要先装VS。否则:安装后打开VS2012新建项目不显示NIVIDA解决方案。记住记住记住!重要的事情说三遍!第一步:安装文件的下载,直接去官网就下载就可以。现在有cuda7.0了。 直接双击exe文件,弹出后,首先会监测一下你的运行环境,如果找不到Nividia对应的显卡设备,他_无法打开包括文件“gtest/gtest.h” :no such file or directory

推荐文章

热门文章

相关标签