python/TangDou/LanQiaoBei/LanQiao12ShengSai/BC4_Shopping_2.cpp

#include <bits/stdc++.h>

using namespace std;
int W; // 可以提起 w 单位重量的东西，
int V; // 有一个能装v个单位体积的购物袋
int n; // 为商品种类数

// 注意多维限制的01背包，一般N值都比较小，100左右，太大就会编译出错了。
const int N = 110;

// 某种商品的重量、体积和让利金额
int a[N], b[N], c[N];

// 在取得最大让利金额的时候，到底是拿了哪些商品？
string s[N][N][N];

// DP数组
int f[N][N][N];

/**
10 9 4
8 3 6
5 4 5
3 7 7
4 5 4

答案:
9
2 4
*/

int main() {
    // 输入
    cin >> W >> V >> n;

    // 每一种商品的重量、体积和让利金额
    for (int i = 1; i <= n; i++) cin >> a[i] >> b[i] >> c[i];

    // 遍历每个种类
    for (int i = 1; i <= n; i++) {
        // 遍历重量(填表)
        for (int j = 1; j <= W; j++) {
            // 遍历体积(填表)
            for (int k = 1; k <= V; k++) {
                int x = f[i - 1][j - a[i]][k - b[i]] + c[i];
                int y = f[i - 1][j][k];

                // 如果剩余的重量和体积都够用的时候,尝试拿当前物品
                if (j >= a[i] && k >= b[i]) {
                    // 也是两个分支，一是不选，另一个是选，要取最大值
                    if (x > y) { // 要上合适
                        f[i][j][k] = x;
                        // 同时记录拿了这个物品
                        s[i][j][k] = s[i - 1][j - a[i]][k - b[i]] + " " + (char)(i + '0');
                    } else // 不要合适
                        f[i][j][k] = y;
                } else { // 装不下，不管是哪种原因装不下，都是这个分支
                    f[i][j][k] = y;
                    // 同时记录不拿当前物品,保持和之前一样的物品列表
                    s[i][j][k] = s[i - 1][j][k];
                }
            }
        }
    }
    // 输出
    cout << f[n][W][V] << endl; // 小惠能够得到的最大让利金额
    string str = s[n][W][V];    // 依次为从小到大排列的商品序号
    cout << str.substr(1, str.size() - 1);
    return 0;
}