[已解决]背包问题在多个背包的情况如何解决？

zhangjinxuan

例如，有 n 个背包，第 i 个背包可以容纳 a_i 的体积，还有 m 个物品，第 i 个物品体积是 v_i，收益是 w_i，你可以把这些物品装在不同的背包中，每个物品只能用 1 次，问最大收益值？

不能两个背包装一个物品

最佳答案

月排行榜 / 总排行榜

柿子饼同学

2023-1-10 13:39:23

zhangjinxuan 发表于 2023-1-9 16:21
我们老师没讲过，难道，这是提高组的

但好像也不对啊，呜呜呜，我去问问

问过了 , 启发式搜索

跳转到最佳答案楼层

zhangjinxuan

@tommyyu @柿子饼同学 @高山 会吗，我抓破脑袋了都没想到

高山

这么简单（自己不会搜搜嘛，很容易搜到的，特别是CSDN）

zhangjinxuan

高山 发表于 2023-1-9 15:26
这么简单（自己不会搜搜嘛，很容易搜到的，特别是CSDN）

这么简单？CSDN? 搜搜？总感觉这话优点……

zhangjinxuan

高山 发表于 2023-1-9 15:26
这么简单（自己不会搜搜嘛，很容易搜到的，特别是CSDN）

不是，关键就是这个状态和转移特别难想，你想，我们怎么判断一个物品拿过还是没有拿过呢？

高山

zhangjinxuan 发表于 2023-1-9 15:28
不是，关键就是这个状态和转移特别难想，你想，我们怎么判断一个物品拿过还是没有拿过呢？

比如map类型，通过0,1代表拿没拿过...

zhangjinxuan

高山 发表于 2023-1-9 15:29
比如map类型，通过0,1代表拿没拿过...

map没啥必要，状态怎么搞？转移怎么办？

要不记录两个状态？

zhangjinxuan

高山 发表于 2023-1-9 15:29
比如map类型，通过0,1代表拿没拿过...

CSDN看了，都是只有一个背包

tommyyu

zhangjinxuan 发表于 2023-1-9 15:32
CSDN看了，都是只有一个背包

我感觉实在不行直接dfs，dp的话可以通过多维vector或者对一个情况转化成数值

zhangjinxuan

tommyyu 发表于 2023-1-9 15:49
我感觉实在不行直接dfs，dp的话可以通过多维vector或者对一个情况转化成数值

dfs时间多大,O(m^n)咧

dp 的话……我也想不明白

tommyyu

zhangjinxuan 发表于 2023-1-9 15:51
dfs时间多大,O(m^n)咧

dp 的话……我也想不明白

比如3个背包，6个物品，状态是这样的：
{
{0, 1, 2},  // 有第0、1、2个物品
{3},
{4, 5}
}
可以通过vector来传递，或者设置一个全局map类型的变量，记录每一种状态所对应的数字，比如{0, 1, 2, 3, 4, 5}对应1，{0}对应2……或者设置一种方法，来将一种情况转化为数字。（这个我实在想不到转化方法）

柿子饼同学

把这些背包容积加起来 , 当成 01 背包问题不就好了
完了 , 好像不对

zhangjinxuan

柿子饼同学 发表于 2023-1-9 16:07
把这些背包容积加起来 , 当成 01 背包问题不就好了
完了 , 好像不对

不能两个背包装一个物品

zhangjinxuan

tommyyu 发表于 2023-1-9 15:58
比如3个背包，6个物品，状态是这样的：
{
{0, 1, 2},  // 有第0、1、2个物品

还是不懂，难道状态的维度还决定背包的数量？

tommyyu

zhangjinxuan 发表于 2023-1-9 16:17
还是不懂，难道状态的维度还决定背包的数量？

只是举的例子

zhangjinxuan

tommyyu 发表于 2023-1-9 16:20
只是举的例子

我们老师没讲过，难道，这是提高组的

但好像也不对啊，呜呜呜，我去问问

ExiaGN001

zhangjinxuan 发表于 2023-1-9 15:28
这么简单？CSDN? 搜搜？总感觉这话优点……

乱CV CSDN代码，某谷屎名警告(bushi

柿子饼同学

zhangjinxuan 发表于 2023-1-9 16:21
我们老师没讲过，难道，这是提高组的

但好像也不对啊，呜呜呜，我去问问

问过了 , 启发式搜索

zhangjinxuan

柿子饼同学 发表于 2023-1-10 13:39
问过了 , 启发式搜索

启发式搜索？

zhangjinxuan

柿子饼同学 发表于 2023-1-10 13:39
问过了 , 启发式搜索

1 <= n <= 100, 1 <= m <= 100 呢？