python/TangDou/LanQiaoBei/LanQiao12ShengSai/BC4.cpp

#include <bits/stdc++.h>

using namespace std;
const int N = 1010;

int n;     //n种蔬菜
int m;     //时间限制(背包容量上限)55
int w[N];  //占用的时间
int v[N];  //销售的价格

// dfs函数定义的意义
// 已经放入背包i个物品，背包剩余体积为j，计算可以获取到的最大价值
int dfs(int i, int j) {
    //保存每一步求得的当前最大价值
    if (i == n + 1) return 0;       //当到n+1个物品时就返回,因为都没有物品可以选择了，你剩余的空间再大，也不会产生价值了，所以是0
    int res;
    //若当前物品的重量大于背包容量时，就无法放入背包。此时，放弃第i个物品，走到i+1个物品前进行下一步尝试
    if (w[i] > j)
        res = dfs(i + 1, j);
    else
        //若能放下，则取放入或不放入两种情况中较大值
        res = max(
                  dfs(i + 1, j),
                  dfs(i + 1, j - w[i]) + v[i]);
    return res;
}

int main() {
    //物品个数与背包容量
    //数据样例: 3 55
    cin >> n >> m;

    //读入每个物品的体积和价值
    /**
     物品个数与背包容量
     种菜的时间花费  售卖价格
     3 55

     21 9
     20 2
     30 21
     */
    for (int i = 1; i <= n; i++)  cin >> w[i] >> v[i];

    //一个没选，剩余空间为m
    cout << dfs(0, m) << endl;
    return 0;
}