背包系列第二篇----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 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
哈哈,博客排版真的漂亮呢~
[***.90.31.176]2024年03月09日 13时33分59秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
mariadb进入mysql命令_mariadb数据库常用命令
2019-04-21
mysql整体会滚_滚mysql
2019-04-21
向mysql数据库中添加批量数据类型_使用JDBC在MySQL数据库中快速批量插入数据
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