背包系列第三篇----01背包(求解最大价值的个数)
发布日期:2021-10-03 20:32:32 浏览次数:2 分类:技术文章

本文共 1409 字,大约阅读时间需要 4 分钟。

一:问题

01背包问题描述:一个容量为V的背包。现在有N种物品,每种只有一个物品,每种物品的体积是C1,C2,…,Cn,对应的每种的价值是W1,W2,…,Wn.。试问,在不超过背包容量的情况下,物品装入背包的最大价值?

什么叫最大价值的个数?

当我们求出一个背包问题的最大价值时,这个最大价值是固定的,但是背包里的物品可能不一样。

二:分析理解

我们设置num[ i ][ j ]二维数组来表示dp[ i ][ j ]的方案数。

我们初始化num[ i ][ j ]为1,因为对每个F[i][j]至少应该有一种方案,即前i件物品中选取若干件物品放入剩余空间为j的背包使其价值最大的方案数至少为1,因为F[i][j]一定存在。

如何求解num[ i ][ j ]需要分三种情况。

1.dp[ i ][ j ] == dp[ i-1 ][ j ]且dp[ i ][ j ] != dp[ i-1 ][ j-Ci ] + Wi 的时候,num[ i ][ j ] = num[ i-1 ][ j ] ;

2.dp[ i ][ j ] != dp[ i-1 ][ j ]且dp[ i ][ j ] == dp[ i-1 ][ j-Ci ] + Wi 的时候,num[ i ][ j ] = num[ i-1 ][ j-Ci ] ;

3.dp[ i ][ j ] == dp[ i-1 ][ j ]且dp[ i ][ j ] == dp[ i-1 ][ j-Ci ] + Wi 的时候,num[ i ][ j ] = num[ i-1 ][ j ]  + num[ i-1 ][ j-Ci ];

这里可以压缩下num[ i ][ j ],压缩成num[ j ],同dp[ i ][ j ]压缩成dp[ j ]一样。

三:代码

#include
#include
using namespace std;#define N 6 #define V 10 //背包容量 int w[N + 1] = { 0,5,3,1,4,6,5 }; //6个物品的价值,第一个0除外 int v[N + 1] = { 0,7,6,5,1,19,7 }; //6个物品的体积,第一个0除外 int dp[V + 5];int num[V + 5];int main(){ fill(num, num + V + 5, 1);//初始设置为1 for (int i = 1; i <= N; i++) { for (int j = V; j >= v[i]; j--) { if (dp[j] < dp[j - v[i]] + w[i]) { dp[j] = dp[j - v[i]] + w[i]; num[j] = num[j - v[i]]; } else if (dp[j] == dp[j - v[i]] + w[i]) num[j] += num[j - v[i]]; } } printf("最大价值是:%d\n", dp[V]); printf("此时背包的最大价值个数是:%d\n", num[V]); return 0;}
四:数据测试

返回背包系列目录--->

转载地址:https://blog.csdn.net/LaoJiu_/article/details/51261788 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:背包系列第四篇----完全背包(求解最大价值)
下一篇:背包系列第二篇----01背包(求解最大价值时背包的物品)

发表评论

最新留言

路过按个爪印,很不错,赞一个!
[***.219.124.196]2024年03月20日 18时25分29秒

关于作者

    喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!

推荐文章

python画多层网络_在pymn中修改多层网络图 2019-04-21
java net 安卓_android -------- java.net.UnknownServiceException 2019-04-21
java 密钥 aes 解密_Java中AES加密解密以及签名校验 2019-04-21
java树转化成图_Java 转换一组数据为树型数据 2019-04-21
java 底层ppt_Java 如何设置 PPT 中的形状排列方式 具体内容 2019-04-21
mysql service5.7_Mysql5.7服务下载安装 2019-04-21
mysql查看线程完整执行命令_MySQL-查看运行的线程-SHOW PROCESSLIST 2019-04-21
mysql 更新数据 字符串_批量替换 MySQL 指定字段中的字符串 2019-04-21
web开发 mysql安装_mysqlinstallerwebcommunity5.7.21.0.msi安装图文教程 2019-04-21
mysql concat 整数型_MySQL 数字类型转换函数(concat/cast) 2019-04-21
mysql单元格函数是_MySQL常用内置函数 2019-04-21
mysql 怎么字段分裂_你可以分裂/爆炸MySQL查询中的字段吗? 2019-04-21
mysql server卸载出错_Mysql卸载问题Start Server卡住报错解决方法 2019-04-21
c语言课程设计工资管理建库,C语言课程设计工资管理系统参考.doc 2019-04-21
c语言case中途跳出,break语句在switch结构语句中的作用是终止某个case,并跳出switch结构语句。... 2019-04-21
C语言编写程序计算高考倒计时天数,基于51单片机LCD12864大字符校时万年历带高考倒计时程序... 2019-04-21
普职融通信息技术课本C语言,“三步走”扎实推进“普职融通”办学新模式 2019-04-21
Android多个签名,【Android】Android批量重签名 2019-04-21
html unicode编码转换,JS实现的Unicode编码转换操作示例 2019-04-21
html页面角落放动漫人物,L2Dwidget.js L2D网页动画人物添加 2019-04-21