文档章节

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

悠悠然然
 悠悠然然
发布于 2017/08/23 09:37
字数 1248
阅读 2912
收藏 29
点赞 3
评论 19

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

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

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

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

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

  • 装包方式:有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,正在进行文档及示例工作,即将正式开源,敬请期待。

© 著作权归作者所有

共有 人打赏支持
悠悠然然

悠悠然然

粉丝 2373
博文 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
XYNUOJ 1416: 竞赛总分

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

dear_jia
03/22
0
0
使用LINGO来解决0/1背包算法问题

原文:使用LINGO来解决0/1背包算法问题 1.问题说明   0/1背包问题:我们有n种物品,物品j的重量为wj,价格为pj。我们假定所有物品的重量和价格都是非负的。背包所能承受的最大重量为W。如果...

杰克.陈
03/23
0
0
动态规划 &

一、 动态规划(Dp问题):解决问题的关键点 1) 递推公式:(最有子结构) 2) 数据的初始化 用例分析: a. 01 背包的问题(Knapsack Problem) 定义: 一个背包的容量V; 存在N个物品:w[i...

Playboy002
2015/07/17
42
0
XYNUOJ 1417: 最小乘车费用

1417: 最小乘车费用时间限制: 1 Sec 内存限制: 128 MB 提交: 16 解决: 8 [提交][状态][讨论版] 题目描述 某条街上每一公里就有一汽车站,乘车费用如下表: 而一辆汽车从不行驶超过10公里。某...

dear_jia
03/22
0
0
背包习题集

一、01背包 题目 有N件物品和一个容量为V的背包。第i件物品的费用是c[i],价值是w[i]。 求解将哪些物 品装入背包可使价值总和最大。 基本思路 这是最基础的背包问题,特点是:每种物品仅有一...

Fire_to_cheat_
2017/11/25
0
0
算法:Dynamic Programing

一、动态规划干嘛的 二、可以解决哪些问题 动态规划一般可分为:线性动规,区域动规,树形动规,背包动规四类。 线性动规:拦截导弹,合唱队形,挖地雷,建学校,剑客决斗等; 区域动规:石子...

猫咪要感冒
2016/10/09
1
0
背包问题 (knapsack problem)

0/1背包问题: 某种限制下的最优问题。整体最优可以由部分最优得到。 由于子问题相交,可以用动态规划方法求解。即,利用空间记录中间计算结果,后续的计算通过简单的判断和查表得到。 中间结...

ChenQi
2012/05/21
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

桌面虚拟化VDI(Virtual Desktop Infrastructure)

为了保证员工(客户)不把公司的资料复制、传输给别人。可以把员工平时办公放在服务器上做。所以使用桌面虚拟化。就是把一个服务器虚拟出很多桌面系统(如:windows)。 桌面虚拟化最大的优势...

王坤charlie
10分钟前
2
0
自我审视及职业规划

啊哈,不知不觉已经工作了3年了。程序员作为一门技术工作,如果分级的话我的能力如何呢?该怎么提升呢? 话说,我现在的能力属于中低级的层次吧,努力在向高级努力。为什么这么说呢: 因为我觉...

一口今心
13分钟前
1
0
《PHP和MySQL Web 开发》 第12章 MySQL高级管理

我决定好好写学习笔记了,对应上书上的目录和重要信息。不瞎jb写了。从这章开始吧,然后之前写的会编辑后重发。嗯,就酱。 12.1 深入理解权限系统 妈蛋 开头就卡住了。。。我先回去修改之前的...

十万猛虎下画山
13分钟前
1
0
Python 3.6:多态的实现

多态的作用不用多说,C++用如下条件来实现多态: 要有继承 要有虚函数函数重写 要有父类指针(父类引用)指向子类对象 实际上C++使用VPTR指针来完成这个事情,其是设计模式的基础,软件分层的基...

全部原谅
14分钟前
0
0
纯Python实现鸢尾属植物数据集神经网络模型[图]

纯Python实现鸢尾属植物数据集神经网络模型[图]: 尝试使用过各大公司推出的植物识别APP吗?比如微软识花、花伴侣等这些APP。当你看到一朵不知道学名的花时,只需要打开植物识别APP,拍摄一张...

原创小博客
16分钟前
0
0
2018安卓巴士开发者大会打造Android技术盛宴

2018安卓巴士开发者大会打造Android技术盛宴2018安卓巴士开发者大会将于8月25日在上海举行,作为中国最具前沿性、专业性的安卓技术会议,将邀请来自爱奇艺、阿里、饿了么等知名企业的一线工程...

逆鳞龙
18分钟前
0
0
Spring框架中的设计模式(二)

Spring框架中的设计模式(二) 原创: 瑞查德-Jack 在 上一篇 中我们在Spring中所谈到的设计模式涉及到了创建模式三剑客和1个行为模式(解释器模式)。这次我们会将眼光更多地关注在具有结构性和...

瑞查德-Jack
18分钟前
1
0
JS基础-DOM Event对象

简介 Event 对象代表事件的状态,比如事件在其中发生的元素、键盘按键的状态、鼠标的位置、鼠标按钮的状态。 事件通常与函数结合使用,函数不会在事件发生前被执行! ==注:详表见《JS基础-...

ZHAO_JH
20分钟前
0
0
tomcat 8.5 远程登录管理页面

1、访问的来源受限注释掉 <?xml version="1.0" encoding="UTF-8"?><!-- Licensed to the Apache Software Foundation (ASF) under one or more contributor license agreements. S......

xixingzhe
27分钟前
0
0
JSON Web Token - 在Web应用间安全地传递信息

JSON Web Token - 在Web应用间安全地传递信息 Sep 06, 2015 in Engineering JSON Web Token(JWT)是一个非常轻巧的规范。这个规范允许我们使用JWT在用户和服务器之间传递安全可靠的信息。 ...

祖冲之
32分钟前
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部