python/TangDou/XiTi/1301.cpp

#include <bits/stdc++.h>

using namespace std;

int n, v, m;        //n:物品件数、v:背包容积,m:背包可承受的最大重量
int f[101][101];   //dp[i][j]:表示总体积是i,重量为j的情况下，最大价值是多少
int a, b, c;        //表示第 i 件物品的体积、重量和价值。

// 二维背包
/*
分析思路
时间复杂度：10^7
每个物品只能用一次->01背包问题
枚举：体积，重量->从大到小枚举
dp[i][j]:表示总体积是i,重量为j的情况下，最大价值是多少
状态转移：
第一层循环：枚举每个物品（从前往后）
第二层循环：枚举体积
第三层循环：枚举重量
 */
int main() {
    //输入+输出重定向
    freopen("../1301.txt", "r", stdin);

    cin >> n >> v >> m;
    //从前往后枚举物品
    for (int i = 0; i < n; i++) {
        cin >> a >> b >> c;
        //体积从大到小枚举
        for (int j = v; j >= a; j--)
            for (int k = m; k >= b; k--) //重量从大到小枚举
                f[j][k] = max(f[j][k], f[j - a][k - b] + c); //状态转移方程
    }
    cout << f[v][m] << endl;
    //关闭文件
    fclose(stdin);
    return 0;
}