背包问题

jsgj2023

有n件物品,第i件物品的重量为c,价格为w,
有一个承重为m的书包,求解将哪些物品装进书包,
使得物品不超重且价格最高.
每种物品只有一件,有放入书包和不放入书包两种状态.

测试数据:
m=10,n=3,
物品重量c[1]=3,c[2]=4,c[3]=5;
物品价格分别为:w[1]=4,w[2]=5,w[3]=6.

小花鹿

感觉要用组合.................................................................................

香川群子

如果数据量小，直接组合遍历求最大值即可。

如果数据量大，那么随机凑满重量以后，遍历检查调整交换即可。（1 vs 1，1 vs 2，2 vs 2）

…………如果有数据例子，可以编程验证。

jsgj2023

香川群子 发表于 2017-6-18 13:27
如果数据量小，直接组合遍历求最大值即可。

如果数据量大，那么随机凑满重量以后，遍历检查调整交换即可 ...

已提供测试数据,老师有空请看看!

香川群子

背包问题的经典解答是动态规划……

三坛老窖

jsgj2023 发表于 2017-6-18 13:38
已提供测试数据,老师有空请看看!

整明白算法原理，写代码就不是什么问题了。
http://blog.csdn.net/mu399/article/details/7722810

香川群子

我是按照我自己的思路来做的。

香川群子

三坛老窖 发表于 2017-6-18 14:52
整明白算法原理，写代码就不是什么问题了。
http://blog.csdn.net/mu399/article/details/7722810

这个算法原理，还是要使用递归检查吧。你有现成的VBA代码吗？如有请提供学习。

我认为，如果数据量很大，难以高效运行。

paciguard

有时间，试试。。。

三坛老窖

香川群子 发表于 2017-6-19 14:46
这个算法原理，还是要使用递归检查吧。你有现成的VBA代码吗？如有请提供学习。

我认为，如果数据量很 ...

你自创的算法得到的结果，不是最优解，且耗时上也没有优势。
我附件中的代码是严格按照链接中的原理写的，能得到最优解，且用你提供的数据，耗时也少于你的代码。
如果数据量大（背包容量大或物品数量多），可用动态规划原理变通解决耗时和内存占用的问题。
DP_01背包.rar (554.29 KB, 下载次数: 171)

2017-6-19 16:00 上传

点击文件名下载附件