震惊:一行代码解决背包问题
震惊:一行代码解决背包问题
悠悠然然 发表于8个月前
震惊:一行代码解决背包问题
  • 发表于 8个月前
  • 阅读 2828
  • 收藏 29
  • 点赞 3
  • 评论 19

【腾讯云】新注册用户域名抢购1元起>>>   

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

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

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

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

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

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

  • 打赏
  • 点赞
  • 收藏
  • 分享
共有 人打赏支持
悠悠然然
粉丝 2345
博文 173
码字总数 360373
作品 14
评论 (19)
开源中国首席技术专家
dpKnapsack 是什么方法?
悠悠然然

引用来自“漆黑的烈焰使”的评论

dpKnapsack 是什么方法?
是自己写好的通用动态规划函数。
开源中国首席技术专家

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

引用来自“漆黑的烈焰使”的评论

dpKnapsack 是什么方法?
是自己写好的通用动态规划函数。

回复@悠悠然然 : 可以发出来看一下吗
jing_rhrh

引用来自“漆黑的烈焰使”的评论

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

引用来自“liverxing”的评论

又一个标题党,如果按照这个意思,岂不是应该说:震惊,一行代码解决任何问题
阐述自己的观点和看法就不能起一个正常点的标题么?哎。
我进来后也在找那一行关键代码,最终发现还是封装成了一个函数方法。。。。
如果这也叫一行代码。。。。
悠悠然然

引用来自“liverxing”的评论

又一个标题党,如果按照这个意思,岂不是应该说:震惊,一行代码解决任何问题
阐述自己的观点和看法就不能起一个正常点的标题么?哎。
你封装一个出来试试看?封装出来我给你6.66赏金。
悠悠然然

引用来自“liverxing”的评论

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

引用来自“xuqingkai”的评论

我进来后也在找那一行关键代码,最终发现还是封装成了一个函数方法。。。。
如果这也叫一行代码。。。。
你封装一个出来试试看?封装出来我给你6.66赏金。
xuqingkai

引用来自“liverxing”的评论

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

引用来自“xuqingkai”的评论

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

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

你封装一个出来试试看?封装出来我给你6.66赏金。
封装就说封装的事,别挂着一个一行代码解决问题的标题
悠悠然然

引用来自“liverxing”的评论

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

引用来自“xuqingkai”的评论

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

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

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

引用来自“xuqingkai”的评论

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

如果我的题目导致你看不下去,向你致歉,请无视即可。
softxyz
我觉得我能写出“一行代码都不用写就解决xxx问题”。
悠悠然然

引用来自“softxyz”的评论

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

回复@softxyz : 嗯嗯,我也绝对相信,你只要放个屁就ok了。
改着名儿玩
震惊!调用一个方法只需要一行代码!
悠悠然然

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

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

回复@改着名儿玩 : 问题是这个方法真的可以解决问题。
xforgchen
我一个按钮将火箭发射上天……楼主既然已经写了,应该将怎么“造火箭”的方法也发出来,不然有标题党之嫌
悠悠然然

引用来自“xforgchen”的评论

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

回复@xforgchen : 嗯嗯,楼主已经把它开源了。
影子明
最近国家打击标题党
softxyz

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

引用来自“softxyz”的评论

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

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

引用来自“softxyz”的评论

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

引用来自“softxyz”的评论

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

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

回复@softxyz : 用代码说话,如果没有代码支持,呵呵....
×
悠悠然然
如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
* 金额(元)
¥1 ¥5 ¥10 ¥20 其他金额
打赏人
留言
* 支付类型
微信扫码支付
打赏金额:
已支付成功
打赏金额: