Project1»广场 › 技术讨论 › RPG Maker XP 讨论区 › 一个背包容量固定，一堆物品有重量，怎样装最接近满 ...

返回列表发新帖

查看: 2505|回复: 3

[已经过期] 一个背包容量固定，一堆物品有重量，怎样装最接近满

梦石: 0
星屑: 1816
在线时间: 2527 小时
注册时间: 2010-10-12
回帖: 1336

发消息

发表于 2014-12-12 12:00:33 | 显示全部楼层 |阅读模式

加入我们，或者，欢迎回来。

您需要登录才可以下载或查看，没有账号？注册会员

×

就是简化版的背包问题，不考虑物品价值的
应该怎样去求最接近满的组合呢
QwQ

评分

参与人数 1	赞 +1	收起理由
玛尔斯	+ 1

查看全部评分

回复

使用道具举报

梦石: 0
星屑: 9557
在线时间: 5074 小时
注册时间: 2013-6-21
回帖: 3459

发消息

发表于 2014-12-12 13:04:39 | 显示全部楼层

这个应该是0-1背包问题的特殊情况。
你可以认为物品的价值=物品的重量，然后按照背包问题求解。
背包问题的代码在我的M考场答卷中，你可以参考下（貌似LZ也参加过M考场吧）。

点评

好吧，后面答卷二字没看到发表于 2014-12-12 18:50

应该是有的吧，没仔细去想。M君我的意思是我在M考场交的答卷啊发表于 2014-12-12 18:47

另外我想说既然价值部分被砍掉了，那么有没有相对应的没有涉及价值的算法? 发表于 2014-12-12 18:44

呃…M考场是我出的发表于 2014-12-12 18:43

哦，好吧- - 发表于 2014-12-12 15:48

RMXP图书馆【常年更新】

回复 

使用道具举报

…あたしは天

梦石
0

星屑
2308

在线时间
4033 小时

注册时间
2010-10-4

回帖
10548

发消息

发表于 2014-12-12 15:45:57 | 显示全部楼层

本帖最后由 taroxd 于 2014-12-12 15:47 编辑

不求最优解的话，贪心算法就行……

点评

尽量最优发表于 2014-12-14 01:14

taroxd.github.io
RPG制作大师授权素材推广计划
Glimmer/Fatal Guise

回复 

使用道具举报

芯☆淡茹水

梦石: 0
星屑: 34464
在线时间: 5096 小时
注册时间: 2012-11-19
回帖: 4715

发消息

发表于 2014-12-13 14:37:20 | 显示全部楼层

接近“最满”的标准是什么？是物品个数+数量；还是额定“重量”的情况下装最多的物品？

点评

背包空间利用率发表于 2014-12-14 01:13

xp vx va mv va mz 各类型脚本/插件定制

回复 

使用道具举报

返回列表发新帖

Archiver|手机版|小黑屋|Project1游戏制作

Powered by Discuz! X5.0 © 2001-2026 Discuz! Team.

在本版发帖返回顶部