AcWing 1022. 宠物小精灵之收服

题目传送门

一、题目解析

不是典型的\(01\)背包问题，而是一个二维费用的背包问题
花费1：精灵球数量
花费2：皮卡丘体力值
价值：小精灵的数量 每一个精灵的价值为\(1\)

二、实现代码

#include 

using namespace std;

const int N = 1010; //野生小精灵的数量上限
const int M = 510;  //小智的精灵球数量上限
int n;              //野生小精灵的数量
int m;              //小智的精灵球数(初始体积1)
int t;              //皮卡丘初始的体力值(初始体积2)
int f[N][M];        //打表数组

int v1[N];          //记录每个小精灵需要消耗的精灵球数量
int v2[N];          //记录每个小精灵需要消耗的皮卡丘体力值

int main() {
    //读入初始体积1和初始体积2，还有一个野生小精灵的数量
    cin >> m >> t >> n;

    //01背包套路
    for (int i = 1; i <= n; i++) { //逐个讨论每个小精灵
        //读入收服当前小精灵需要花费的精灵球数量和消耗的皮卡丘体力值
        cin >> v1[i] >> v2[i];
        //一维容量从高到低
        for (int j = m; j >= v1[i]; j--)
            //二维容量从高到低,需要注意的是皮卡丘的体力值最后不能为零~~~
            for (int k = t - 1; k >= v2[i]; k--)
                f[j][k] = max(f[j][k], f[j - v1[i]][k - v2[i]] + 1);
    }
    //输出最优个数解
    printf("%d ", f[m][t - 1]);
    //找到满足最大价值的所有状态里，第二维费用消耗最少的
    int k = 0;
    while (f[m][k] != f[m][t - 1]) k++;
    //皮卡丘的剩余体力值
    printf("%d", t - k);
    return 0;
}