二维费用01背包问题

背包问题需要抽象出：背包的体积、价值

根据该题，每个精灵消耗的精灵球、体力是体积，总体积是精灵球总数和体力，因为要小精灵数量尽可能的多，所以小精灵的价值都看成一样即可，即1。

边界：因为体力如果为0了，则这个小精灵是收复不了的，所以体力最多是V - 1。

对于第二问来说，最多收复c个小精灵时，剩余的最大体力是多少？

剩余最大体力即求收复c个小精灵最小花费体力是多少。

因为f[v1][v2]是表示花费1不超过v1,花费2不超过v2的收复小精灵的最大数量。如果我们要求最小花费的体力。

则：

$ 时间复杂度O(NMK)，空间复杂度O(MK)$

参考文献

算法题高课

AC代码

#include <iostream>
using namespace std;

const int N = 1010, M = 510;

int f[N][M];
int v1[N], v2[N];
int n , m , k;

int main(){
    //输出
    cin >> m >> k >> n;
    for (int i = 0 ; i < n ; i ++) cin >> v1[i] >> v2[i];

    //DP
    for (int i = 0 ; i < n ; i ++){
        for (int j = m ; j >= v1[i] ; j--){
            for (int l = k - 1 ; l >= v2[i] ; l --){
                f[j][l] = max(f[j][l], f[j - v1[i]][l - v2[i]] + 1);
            }
        }
    }

    //求最小消耗体力能收复c个小精灵
    int r = k - 1;
    while (r > 0 && f[m][r - 1] == f[m][k - 1]) r --;

    //输出
    cout << f[m][k - 1] << " " << k - r << endl;

    return 0;
}