背包问题在多个背包的情况如何解决？
本帖最后由 zhangjinxuan 于 2023-1-9 11:51 编辑例如，有 n 个背包，第 i 个背包可以容纳 ai 的体积，还有 m 个物品，第 i 个物品体积是 vi，收益是 wi，你可以把这些物品装在不同的背包中，每个物品只能用 1 次，问最大收益值？
不能两个背包装一个物品 @tommyyu @柿子饼同学 @高山 会吗，我抓破脑袋了都没想到{:10_291:} 这么简单（自己不会搜搜嘛，很容易搜到的，特别是CSDN） 高山 发表于 2023-1-9 15:26
这么简单（自己不会搜搜嘛，很容易搜到的，特别是CSDN）
这么简单？CSDN? 搜搜？总感觉这话优点…… 高山 发表于 2023-1-9 15:26
这么简单（自己不会搜搜嘛，很容易搜到的，特别是CSDN）
不是，关键就是这个状态和转移特别难想，你想，我们怎么判断一个物品拿过还是没有拿过呢？ zhangjinxuan 发表于 2023-1-9 15:28
不是，关键就是这个状态和转移特别难想，你想，我们怎么判断一个物品拿过还是没有拿过呢？
比如map类型，通过0,1代表拿没拿过... 高山 发表于 2023-1-9 15:29
比如map类型，通过0,1代表拿没拿过...
map没啥必要，状态怎么搞？转移怎么办？
要不记录两个状态？ 高山 发表于 2023-1-9 15:29
比如map类型，通过0,1代表拿没拿过...
CSDN看了，都是只有一个背包{:10_266:} zhangjinxuan 发表于 2023-1-9 15:32
CSDN看了，都是只有一个背包
我感觉实在不行直接dfs，dp的话可以通过多维vector或者对一个情况转化成数值 tommyyu 发表于 2023-1-9 15:49
我感觉实在不行直接dfs，dp的话可以通过多维vector或者对一个情况转化成数值
dfs时间多大,O(m^n)咧
dp 的话……我也想不明白 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……或者设置一种方法，来将一种情况转化为数字。（这个我实在想不到转化方法） 本帖最后由 柿子饼同学 于 2023-1-9 16:08 编辑
把这些背包容积加起来 , 当成 01 背包问题不就好了
完了 , 好像不对 柿子饼同学 发表于 2023-1-9 16:07
把这些背包容积加起来 , 当成 01 背包问题不就好了
完了 , 好像不对
不能两个背包装一个物品 tommyyu 发表于 2023-1-9 15:58
比如3个背包，6个物品，状态是这样的：
{
{0, 1, 2},// 有第0、1、2个物品
还是不懂，难道状态的维度还决定背包的数量？ zhangjinxuan 发表于 2023-1-9 16:17
还是不懂，难道状态的维度还决定背包的数量？
只是举的例子{:10_282:} tommyyu 发表于 2023-1-9 16:20
只是举的例子
我们老师没讲过，难道，这是提高组的{:10_266:}
但好像也不对啊，呜呜呜，我去问问{:10_250:} zhangjinxuan 发表于 2023-1-9 15:28
这么简单？CSDN? 搜搜？总感觉这话优点……
乱CV CSDN代码，某谷屎名警告(bushi zhangjinxuan 发表于 2023-1-9 16:21
我们老师没讲过，难道，这是提高组的
但好像也不对啊，呜呜呜，我去问问
问过了 , 启发式搜索 柿子饼同学 发表于 2023-1-10 13:39
问过了 , 启发式搜索
启发式搜索？ 柿子饼同学 发表于 2023-1-10 13:39
问过了 , 启发式搜索
1 <= n <= 100, 1 <= m <= 100 呢？
页:
[1]
2