带类型约束的多属性背包问题求解及代码相关疑问

问题定义 #

在经典0-1背包基础上新增类型约束：每种类型的物品最多选择一个，要求在总重量不超过背包容量的前提下，最大化所选物品的总价值。给定示例数据：

int weights[5] = {1, 3, 5, 9, 10};
int values[5] = {11, 13, 1, 19, 9};
int types[5] = {1,2,1,3,4};
int capacity = 26;

原代码问题分析 #

你提供的递归记忆化实现存在核心逻辑错误：

• 全局set<int> ttypes会在递归分支间共享状态，导致不同递归路径互相干扰，无法正确记录每个分支的已选类型。
• 3D数组t2的维度设计不合理，第三维存储当前物品类型无法有效记录状态，正确的状态应包含已处理的类型组和剩余容量。
• 初始化时memset(t, -1, sizeof(t))中的变量t未定义，应为t2，且后续遍历整个数组找最大值的逻辑冗余。

正确解法：分组背包问题转化 #

这类带类型约束的背包本质是分组背包问题：将同类型物品划分为一组，每组最多选择一个物品（或不选）。以下是两种实现方式：

1. 迭代动态规划（推荐） #

通过滚动数组优化空间，时间复杂度为O(GCK)，其中G是类型组数，C是背包容量，K是每组的物品数。

#include <iostream>
#include <vector>
#include <unordered_map>
#include <algorithm>
using namespace std;

int main() {
    int weights[5] = {1, 3, 5, 9, 10};
    int values[5] = {11, 13, 1, 19, 9};
    int types[5] = {1,2,1,3,4};
    int capacity = 26;

    // 按类型分组
    unordered_map<int, vector<pair<int, int>>> type_groups;
    for (int i = 0; i < 5; ++i) {
        type_groups[types[i]].emplace_back(weights[i], values[i]);
    }
    vector<vector<pair<int, int>>> groups;
    for (auto& p : type_groups) {
        groups.push_back(p.second);
    }

    // dp[j]表示容量为j时的最大价值
    vector<int> dp(capacity + 1, 0);

    // 遍历每个类型组
    for (auto& group : groups) {
        // 倒序遍历容量，避免重复选择同组物品
        for (int j = capacity; j >= 0; --j) {
            for (auto& item : group) {
                int w = item.first;
                int v = item.second;
                if (j >= w) {
                    dp[j] = max(dp[j], dp[j - w] + v);
                }
            }
        }
    }

    cout << dp[capacity] << endl; // 输出52
    return 0;
}

2. 递归记忆化实现 #

状态定义为memo[group_idx][remaining_w]，表示处理到第group_idx个类型组、剩余容量为remaining_w时的最大价值。

#include <iostream>
#include <vector>
#include <unordered_map>
#include <algorithm>
using namespace std;

vector<vector<int>> memo;
vector<vector<pair<int, int>>> groups;

int dfs(int group_idx, int remaining_w) {
    // 边界条件：处理完所有组或剩余容量为0
    if (group_idx == groups.size() || remaining_w <= 0) {
        return 0;
    }
    // 已记忆的状态直接返回
    if (memo[group_idx][remaining_w] != -1) {
        return memo[group_idx][remaining_w];
    }

    // 不选当前组的任何物品
    int max_val = dfs(group_idx + 1, remaining_w);
    // 尝试选择当前组的每个物品
    for (auto& item : groups[group_idx]) {
        int w = item.first;
        int v = item.second;
        if (remaining_w >= w) {
            max_val = max(max_val, v + dfs(group_idx + 1, remaining_w - w));
        }
    }

    return memo[group_idx][remaining_w] = max_val;
}

int main() {
    int weights[5] = {1, 3, 5, 9, 10};
    int values[5] = {11, 13, 1, 19, 9};
    int types[5] = {1,2,1,3,4};
    int capacity = 26;

    unordered_map<int, vector<pair<int, int>>> type_groups;
    for (int i = 0; i < 5; ++i) {
        type_groups[types[i]].emplace_back(weights[i], values[i]);
    }
    for (auto& p : type_groups) {
        groups.push_back(p.second);
    }

    // 初始化记忆数组，-1表示未访问
    memo.assign(groups.size(), vector<int>(capacity + 1, -1));
    cout << dfs(0, capacity) << endl; // 输出52
    return 0;
}

新增体积约束的实现 #

若物品新增体积属性，背包同时受重量和容量限制，此时为二维分组背包，状态扩展为dp[w][v]，表示重量不超过w、体积不超过v时的最大价值：

#include <iostream>
#include <vector>
#include <unordered_map>
#include <algorithm>
#include <tuple>
using namespace std;

int main() {
    int weights[5] = {1, 3, 5, 9, 10};
    int values[5] = {11, 13, 1, 19, 9};
    int types[5] = {1,2,1,3,4};
    int volumes[5] = {2, 4, 1, 5, 3}; // 新增体积属性
    int max_weight = 26;
    int max_volume = 30; // 体积容量

    // 按类型分组，存储(重量, 体积, 价值)
    unordered_map<int, vector<tuple<int, int, int>>> type_groups;
    for (int i = 0; i < 5; ++i) {
        type_groups[types[i]].emplace_back(weights[i], volumes[i], values[i]);
    }
    vector<vector<tuple<int, int, int>>> groups;
    for (auto& p : type_groups) {
        groups.push_back(p.second);
    }

    // dp[w][v]表示重量w、体积v下的最大价值
    vector<vector<int>> dp(max_weight + 1, vector<int>(max_volume + 1, 0));

    for (auto& group : groups) {
        // 倒序遍历重量和体积，避免重复选同组物品
        for (int w = max_weight; w >= 0; --w) {
            for (int v = max_volume; v >= 0; --v) {
                for (auto& item : group) {
                    int wi = get<0>(item);
                    int vi = get<1>(item);
                    int val = get<2>(item);
                    if (w >= wi && v >= vi) {
                        dp[w][v] = max(dp[w][v], dp[w - wi][v - vi] + val);
                    }
                }
            }
        }
    }

    cout << dp[max_weight][max_volume] << endl;
    return 0;
}

记忆化方式对比：数组 vs Map #

• 数组（3D/二维）：
  • 优势：访问速度O(1)，无额外哈希或树结构开销，适合状态密集的背包问题。
  • 劣势：需要提前知晓状态的最大范围（如组数、容量），若范围极大可能占用过多内存。
• Map/Unordered_map：
  • 优势：无需提前确定状态范围，适合状态稀疏的场景。
  • 劣势：访问速度慢（Map为O(log n)，Unordered_map平均O(1)但有哈希冲突开销），递归中频繁查询会显著降低效率。

综上，背包问题这类状态密集的场景，数组类记忆化是最优选择。

内容的提问来源于stack exchange，提问作者scarecrow