当前位置:网站首页>详解背包问题(DP分支)
详解背包问题(DP分支)
2022-08-03 05:18:00 【xyc20120615】
目录
什么是背包问题?
要吃透背包问题,就得先知道背包问题是个啥,所以我从百度摘了些内容:
背包问题(Knapsack problem)是一种组合优化的NP完全问题。问题可以描述为:给定一组物品,每种物品都有自己的重量和价格,在限定的总重量内,我们如何选择,才能使得物品的总价格最高。问题的名称来源于如何选择最合适的物品放置于给定背包中。相似问题经常出现在商业、组合数学,计算复杂性理论、密码学和应用数学等领域中。也可以将背包问题描述为决定性问题,即在总重量不超过W的前提下,总价值是否能达到V?它是在1978年由Merkle和Hellman提出的。
背包问题已经研究了一个多世纪,早期的作品可追溯到1897年数学家托比亚斯·丹齐格(Tobias Dantzig,1884-1956)的早期作品,并指的是包装你最有价值或有用的物品而不会超载你的行李的常见问题。
是不是感觉很晦涩很难懂?
所以我编了些例题:
例题一:
小李子的摸底测考试成绩出来了,他的进步很大!所以他的爸妈决定带着高兴的小李子前往阿穷便利店进行零食大采购!每种零食都会有它的价格和它对于小李子的价值,由于他爸妈严格的价格限制,他只能在价格限制中购买零食。你作为他就在刚刚结实的好朋友,能够使他在价格限制中获取最高的价值吗?(从便利店的名字里就能够看出来,这家便利店十分贫穷,所以老板要求每种零食只能买一份)
例题二:
小李子的期中考试成绩出来了,他得了100分!所以他的爸妈决定带着几近疯狂的小李子前往富丽堂皇便利店进行疯狂零食大采购!每种零食都会有它的价格和它对于小李子的价值,由于他爸妈严格的价格限制,他只能在价格限制中购买零食。你作为他就在刚刚结实的好朋友,能够使他在价格限制中获取最高的价值?(从便利店的名字里就能够看出来,这家便利店十分富裕,所以老板同意每种零食可以买无数份)
例题三:
小李子的期中考试成绩出来了,他得了98分!所以他的爸妈决定带着开心的小李子前往富丽堂皇便利店进行超级零食大采购!每种零食都会有它的价格和它对于小李子的价值,由于他爸妈严格的价格限制,他只能在价格限制中购买零食。你作为他就在刚刚结实的好朋友,能够使他在价格限制中获取最高的价值吗?(从便利店的名字里就能够看出来,这家便利店十分富裕,所以老板同意每种零食可以买无数份,可是因为小李子退步了一些,所以他爸妈给每种零食都设置了一个购买数量的限额)
很多眼尖的大佬可能就已经看出来了,这三道题分别就是0/1背包,完全背包以及多重背包的经典例题,可以说大多数背包问题都是这三种。
这三种经典例题对应的题解如下:
看懂了这些例题,接下来就请出我们亲爱的
水题,变形例题以及其他背包们:
水题们:
0/1背包:
由于采药实在太水了就没有写
完全背包:
多重背包:
变形例题:
0/1背包:
完全背包:
其他背包:
—————————————————————~end~———————————————————
边栏推荐
猜你喜欢
随机推荐
Makefile介绍
浏览器多线程离屏渲染压缩打包方案
C语言简单实现扫雷小游戏
ansible的安装和部署详细过程,配置清单基本操作
C语言简单实现三子棋小游戏
【DC-5靶场渗透】
ss-4.1-1个eurekaServer+1个providerPayment+1个consumerOrder
动态规划笔记
3n+1问题
Go (一) 基础部分2 -- if条件判断,for循环语句
浅谈函数递归汉诺塔
详解Nurbs曲线
编写一个函数 reverse_string(char * string)(两种方法实现)7.26
icebreaker的垃圾话学习指南
ss-2.子项目互相访问(order80 -> payment8001)
web安全-sql注入漏洞
【Nmap与Metasploit常用命令】
Benchmark 第一篇 了解Benchmark
D-PHY
【反弹shell与提权】