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

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

一:问题

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

经过第一篇的学习,我们学会求解最大价值,而此篇是在求出最大价值的同时,也要求出背包内有哪么物品?这是一个记录路径问题。

二:分析理解

我们设置一个path[][]二维数组记录路径。

这不是很难,看代码应该能看懂。

三:代码

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

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

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

上一篇:背包系列第三篇----01背包(求解最大价值的个数)
下一篇:hdu2844 Coins --多重背包

发表评论

最新留言

哈哈,博客排版真的漂亮呢~
[***.90.31.176]2024年03月09日 13时33分59秒

关于作者

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

推荐文章

mariadb进入mysql命令_mariadb数据库常用命令 2019-04-21
mysql 安装 linux 系统内核_linux2.6内核下的mysql5.5通用包部署 2019-04-21
mysql整体会滚_滚mysql 2019-04-21
向mysql数据库中添加批量数据类型_使用JDBC在MySQL数据库中快速批量插入数据 2019-04-21
最全的mysql 5.7.13_最全的mysql 5.7.13 安装配置方法图文教程(linux) 强烈推荐! 2019-04-21
mssql连接mysql数据库文件_在本地 怎么远程连接MSSQL数据库 2019-04-21
mssql 远程无法连接mysql_解决SQLServer远程连接失败的问题 2019-04-21
linux mysql c++编程_Linux下进行MYSQL的C++编程起步手记 2019-04-21
Maria数据库怎么复制到mysql_MySQL、MariaDB数据库的AB复制配置过程 2019-04-21
mysql5.6 icp mrr bak_【mysql】关于ICP、MRR、BKA等特性 2019-04-21
mysql utf8跟utf8mb4_MySQL utf8 和 utf8mb4 的区别 2019-04-21
beego mysql 生成_beego 代码生成工具体验 2019-04-21
docker mysql开机自启动_Docker学习4-学会如何让容器开机自启服务【坑】 2019-04-21
在mysql中删除表正确的是什么_在MySQL中删除表的操作教程 2019-04-21
mysql有3个共同好友_共同好友mysql 2019-04-21
代理查询 mysql_查询数据库代理设置 2019-04-21
mysql dif_mysqldiff实现MySQL数据表比较 2019-04-21
mysql 允许其他主机访问权限_允许其他主机访问本机MySQL 2019-04-21
druid不能close mysql连接_alibaba druid mysql连接问题 2019-04-21
mysql 设置按天分表_MySQL 优化实战记录 2019-04-21