“多个约束背包问题”用C++语言求解

多个约束背包问题是指在有限的容量下，选择若干个物品放入背包，使得这些物品的总价值最大，同时满足多个约束条件，例如每个物品的体积、重量、颜色等属性都有限制。这里提供一种基于深度优先搜索的求解方法。

#include <iostream>
#include <cstring>
using namespace std;

const int N = 110;

int n, m;
int v[N], w[N], s[N]; // v表示体积，w表示价值，s表示数量
int maxv[N], maxw[N]; // maxv表示最大体积，maxw表示最大价值
bool vis[N]; // 标记数组，记录物品是否被选中

void dfs(int depth, int curv, int curw)
{
    if (depth == n + 1) { // 达到叶子节点，更新最大价值和体积
        for (int i = 0; i <= m; i++) {
            maxv[i] = max(maxv[i], curv);
            maxw[i] = max(maxw[i], curw);
        }
        return;
    }
    for (int i = 0; i <= s[depth]; i++) { // 枚举第depth个物品选择的个数
        if (curv + v[depth] * i <= m && curw + w[depth] * i <= maxw[curv + v[depth] * i]) { // 剪枝
            vis[depth] = true;
            dfs(depth + 1, curv + v[depth] * i, curw + w[depth] * i);
            vis[depth] = false;
        }
    }
}

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> v[i] >> w[i] >> s[i];
    }
    memset(maxv, -1, sizeof maxv);
    memset(maxw, -1, sizeof maxw);
    maxv[0] = 0, maxw[0] = 0;
    dfs(1, 0, 0);
    cout << maxw[m] << endl;

    return 0;
}

在上述代码中，dfs函数表示深度优先搜索，curv表示当前体积，curw表示当前价值，maxv和maxw分别表示最大体积和最大价值，通过枚举第depth个物品选择的个数，可以得到curv和curw的更新。同时，通过剪枝操作，可以减少搜索次数，提高效率。最终，输出maxw[m]即为最大价值。