宠物小精灵之收服

标签：二维01背包问题

1.为什么是01背包问题

首先从题意下手，每个小精灵的个数只有一个，只有两种选择，要么收服，要么不收服，符合经典的01背包的两种操作

2.为什么是2维背包问题

因为题目说的很明确，在收服小精灵的时候，需要考虑的元素包括精灵球的个数，皮卡丘的剩余血量，只有两者都满足的前提下才能将小精灵收服

3.传统的二维01背包问题求解模板：

for(i:遍历所有的小精灵)
    for(j:从大到小遍历所有的精灵球数)
        for(k:从大到小遍历所有的血量值)
            if(血量也够，精灵球也够)
                d[j][k] = max(d[j,k],d[j-球数][k-血数] + 1);

解题代码如下：

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1010;

int n, m, k;
int v[N], w[N];
int d[N][N];

int main()
{
    scanf("%d%d%d", &n, &m, &k);
    for(int i = 1; i <= k; i ++ )
        scanf("%d%d", &v[i], &w[i]);

    for(int i = 1; i <= k; i ++ )
    {
        for(int j = n; j >= v[i]; j -- )
        {
            for(int z = m; z >= w[i]; z -- )
            {
                d[j][z] = max(d[j][z], d[j - v[i]][z - w[i]] + 1);
            }
        }
    }

    //找出所有收集的宠物最多且代价最小的
    int res = -1, t;
    for(int j = 0; j <= n; j++) 
    {
        //得保证皮卡丘不能挂了，所以k是 < m 而不是 <= m
        for(int k = 0; k < m; k++)
        {
            //1.如果捕捉到的小精灵数比之前大，则更新
            //2.如果捕捉到的小精灵数和最大的一样，但是消耗的体力更小，则更新
            if(d[j][k] > res || (res == d[j][k] && k < t)) 
            {
                res = d[j][k], t = k;
            }
        }
    }

    cout<<res<<" "<<m - t;

    return 0;
}