文档章节

震惊:一行代码解决背包问题

悠悠然然
 悠悠然然
发布于 2017/08/23 09:37
字数 1248
阅读 3052
收藏 29

背包问题是一个非常典型的问题,围绕他的算法及文章非常多。

实际上本人觉得作为一个程序员,肯定不是碰到一个问题就写一个方式,肯定希望我只要提供简单的几步就搞定我想要的结果,而不是去钻研算法本身。

我把背包问题做了几个抽象:

  • 总容量:不管是容积、重量、金钱等等,只要是受限制的,那么就都是一种意义上的总容量

  • 单个容量:每个物品的容积、重量、单价等等,都是一种意义上的单个容量

  • 装包方式:有01,完全、混合、多重等等各种变种

  • 单个价值评估:给出每个物品的价值

至于如果动态规划及价值累计,那就不是使用的人关心的了。

震惊:一行代码解决背包问题

数据准备

上面定义了,一个物品的类,它有name,weight,value三个属性;有一个构造函数,没有函数体表示把参数的值赋给属性;下面建立了一个物品列表。

好的,准备工作就绪,见证奇迹的时刻就要到来了:

  • 01背包解法

list=[
new Obj("a",2,6.0),
new Obj("b",2,3.0),
new Obj("c",6,5.0),
new Obj("d",5,4.0),
new Obj("e",4,6.0)
];
println("01背包问题:"+list.dpKnapsack(10,list.weight,1,list.value));

上面的含义是:对这个list中的物品进行01背包方式进行获取的最大价值是多少及其获取方法。参数解释:

10:最大重量10

list.weight:物品的重量列表

1:表示每个物品都是最多1个

运行结果:

01背包问题:

[
{result=15.0}, 
[Obj[name=a,weight=2,value=6.0], Obj[name=b,weight=2,value=3.0], Obj[name=e,weight=4,value=6.0]], 
[1, 1, 1]
]

结果解释:

{result=15.0}表示,最后取出来的最大价值

[Obj[name=a,weight=2,value=6.0], Obj[name=b,weight=2,value=3.0], Obj[name=e,weight=4,value=6.0]]表示最后取出来的3个物品。

[1, 1, 1]表示每个物品的取出数量,下标顺序和物品相对应。

  • 完全背包解法

list=[
new Obj("a",2,6.0),
new Obj("b",2,3.0),
new Obj("c",6,5.0),
new Obj("d",5,4.0),
new Obj("e",4,6.0)
];
println("完全背包问题:"+list.dpKnapsack(10,list.weight,list.value));

上面的含义是:对这个list中的物品进行完全背包方式进行获取的最大价值是多少及其获取方法。参数解释:

10:最大重量10

list.weight:物品的重量列表

list.value:每个物品的价值列表

运行结果:

完全背包问题:

[{result=30.0}, [Obj[name=a,weight=2,value=6.0]], [5]]

结果解释:

{result=30.0}表示,最后取出来的最大价值

[Obj[name=a,weight=2,value=6.0]]表示最后取出来的物品列表。

[5]表示每个物品的取出数量,下标顺序和物品相对应。

  • 多重背包

list=[
new Obj("a",12,4.0),
new Obj("b",2,2.0),
new Obj("c",1,1.0),
new Obj("d",4,10.0),
new Obj("e",1,2.0)
];

println("多重背包问题:"+list.dpKnapsack(15,list.weight,[1,7,12,3,1],list.value));

上面的含义是:对这个list中的物品进行多重背包方式进行获取的最大价值是多少及其获取方法。参数解释:

15:最大重量15

list.weight:物品的重量列表

[1,7,12,3,1]:表示每个物品对应最多个数

list.value:每个物品对应的价值

运行结果:

多重背包问题:

[
{result=34.0}, 
[Obj[name=b,weight=2,value=2.0], Obj[name=d,weight=4,value=10.0], Obj[name=e,weight=1,value=2.0]], 
[1, 3, 1]
]

结果解释:

{result=34.0}表示,最后取出来的最大价值

[Obj[name=b,weight=2,value=2.0], Obj[name=d,weight=4,value=10.0], Obj[name=e,weight=1,value=2.0]]表示最后取出来的3个物品。

[1, 3, 1]表示每个物品的取出数量,下标顺序和物品相对应。

  • 混合背包

list=[
new Obj("a",12,4.0),
new Obj("b",2,2.0),
new Obj("c",1,1.0),
new Obj("d",4,10.0),
new Obj("e",1,2.0)
];

println("多重背包问题:"+list.dpKnapsack(15,list.weight,[1,7,12,3,-1],list.value));

上面的含义是:对这个list中的物品进行多重背包方式进行获取的最大价值是多少及其获取方法。参数解释:

15:最大重量15

list.weight:物品的重量列表

[1,7,12,3,-1]:表示每个物品对应最多个数,-1表示不限制次数

list.value:每个物品对应的价值

运行结果:

多重背包问题:

[
{result=36.0}, 
[Obj[name=d,weight=4,value=10.0], Obj[name=e,weight=1,value=2.0]], 
[3, 3]
]

结果解释:

{result=36.0}表示,最后取出来的最大价值

[Obj[name=d,weight=4,value=10.0], Obj[name=e,weight=1,value=2.0]]表示最后取出来的物品列表。

[3, 3]表示每个物品的取出数量,下标顺序和物品相对应。

这次的示例都是典型的背包问题,下次讲带来深入解决实际问题的示例,感兴趣的同学请关注我,以便及时收到推送。

注:此次语言采用本人新作tinyscript,正在进行文档及示例工作,即将正式开源,敬请期待。

© 著作权归作者所有

共有 人打赏支持
悠悠然然

悠悠然然

粉丝 2381
博文 184
码字总数 360373
作品 14
杭州
架构师
加载中

评论(19)

悠悠然然
悠悠然然

引用来自“softxyz”的评论

引用来自“悠悠然然”的评论

引用来自“softxyz”的评论

我觉得我能写出“一行代码都不用写就解决xxx问题”。

回复@softxyz : 嗯嗯,我也绝对相信,你只要放个屁就ok了。
只要你封装的好,用户连代码都不用写就能解决问题,连放个:dash:都不用的。

回复@softxyz : 用代码说话,如果没有代码支持,呵呵....
softxyz
softxyz

引用来自“悠悠然然”的评论

引用来自“softxyz”的评论

我觉得我能写出“一行代码都不用写就解决xxx问题”。

回复@softxyz : 嗯嗯,我也绝对相信,你只要放个屁就ok了。
只要你封装的好,用户连代码都不用写就能解决问题,连放个:dash:都不用的。
影子明
影子明
最近国家打击标题党
悠悠然然
悠悠然然

引用来自“xforgchen”的评论

我一个按钮将火箭发射上天……楼主既然已经写了,应该将怎么“造火箭”的方法也发出来,不然有标题党之嫌

回复@xforgchen : 嗯嗯,楼主已经把它开源了。
xforgchen
xforgchen
我一个按钮将火箭发射上天……楼主既然已经写了,应该将怎么“造火箭”的方法也发出来,不然有标题党之嫌
悠悠然然
悠悠然然

引用来自“改着名儿玩”的评论

震惊!调用一个方法只需要一行代码!

回复@改着名儿玩 : 问题是这个方法真的可以解决问题。
改着名儿玩
改着名儿玩
震惊!调用一个方法只需要一行代码!
悠悠然然
悠悠然然

引用来自“softxyz”的评论

我觉得我能写出“一行代码都不用写就解决xxx问题”。

回复@softxyz : 嗯嗯,我也绝对相信,你只要放个屁就ok了。
softxyz
softxyz
我觉得我能写出“一行代码都不用写就解决xxx问题”。
悠悠然然
悠悠然然

引用来自“liverxing”的评论

又一个标题党,如果按照这个意思,岂不是应该说:震惊,一行代码解决任何问题
阐述自己的观点和看法就不能起一个正常点的标题么?哎。

引用来自“xuqingkai”的评论

我进来后也在找那一行关键代码,最终发现还是封装成了一个函数方法。。。。
如果这也叫一行代码。。。。

引用来自“悠悠然然”的评论

你封装一个出来试试看?封装出来我给你6.66赏金。

引用来自“xuqingkai”的评论

封装就说封装的事,别挂着一个一行代码解决问题的标题
别那么钻牛角尖,事实也确实是只用了一行代码就解决了多种背包问题,当然这源于我们使用的脚本里面内嵌了通用的DP算法,我又没有说用java或C一行代码解决。所以,把时间了精力放在“这个函数是怎么写的?我如果做的话怎么可以做到?”上面对你更有帮助。

如果我的题目导致你看不下去,向你致歉,请无视即可。
动态规划之01背包问题(python实现)

动态规划之01背包问题python实现 背包问题(Knapsack problem)是一种组合优化的NP完全问题。 问题描述为:给定一组物品,每种物品都有自己的重量和价格,在限定的总重量内,我们如何选择,才能...

qq_34178562
04/16
0
0
详解动态规划01背包问题--JavaScript实现

一开始在接触动态规划的时候,可能会云里雾里,似乎能理解思路,但是又无法准确地表述或者把代码写出来。本篇将一步一步通过作图的方式帮助初次接触动态规划的同学来理解问题。这一篇将以经典...

YinTokey
05/19
0
0
XYNUOJ 1435 混合背包

1435: 混合背包时间限制: 1 Sec 内存限制: 128 MB 提交: 8 解决: 8 [提交][状态][讨论版] 题目描述 一个旅行者有一个最多能用V公斤的背包,现在有n件物品,它们的重量分别是W1,W2,...,Wn,...

dear_jia
03/23
0
0
js算法初窥05(算法模式02-动态规划与贪心算法)

  在前面的文章中(js算法初窥02(排序算法02-归并、快速以及堆排)我们学习了如何用分治法来实现归并排序,那么动态规划跟分治法有点类似,但是分治法是把问题分解成互相独立的子问题,最...

zaking
05/29
0
0
XYNUOJ 1416: 竞赛总分

1416: 竞赛总分时间限制: 1 Sec 内存限制: 128 MB 提交: 12 解决: 11 [提交][状态][讨论版] 题目描述 学生在我们USACO的竞赛中的得分越多我们越高兴。 我们试着设计我们的竞赛以便人们能尽可...

dear_jia
03/22
0
0

没有更多内容

加载失败,请刷新页面

加载更多

74.expect脚本同步文件以及指定host同步文件 构建分发系统文件和命令

20.31 expect脚本同步文件: 在expect脚本中去实现在一台机器上把文件同步到另外一台机器上去。核心命令用的是rsync ~1.自动同步文件 #!/usr/bin/expect set passwd "123456" spawn rsync -a...

王鑫linux
19分钟前
0
0
TypeScript项目引用(project references)

转发 TypeScript项目引用(project references) TypeScript新特性之项目引用(project references) 项目引用是TypeScript 3.0中的一项新功能,允许您将TypeScript程序构建为更小的部分。 通过这...

durban
24分钟前
0
0
爬虫入门

导读 网络爬虫(Web crawler),是一种按照一定的规则,自动地抓取万维网信息的程序或者脚本,它们被广泛用于互联网搜索引擎或其他类似网站,可以自动采集所有其能够访问到的页面内容,以获取...

问题终结者
24分钟前
0
0
ppwjs之bootstrap文字排版:无序列表项不换行

<!DOCTYPT html><html><head><meta http-equiv="content-type" content="text/html; charset=utf-8" /><title>ppwjs欢迎您</title><link rel="icon" href="/favicon.ico" ......

ppwjs
31分钟前
0
0
SpringBoot 学习一

本文将从以下几个方面介绍: 前言 HelloWorld 读取配置文件 例子(CURD) 前言 Spring Boot是由Pivotal团队提供的全新框架,其设计目的是用来简化新Spring应用的初始搭建以及开发过程。该框架...

tsmyk0715
31分钟前
1
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部