AcWing 1022. 宠物小精灵之收服

宠物小精灵之收服(二维费用背包问题)

原题链接：https://www.acwing.com/problem/content/1024/

思路

先做一个阅读理解

每一个小精灵只能收一次->01背包
接下来去考虑体积、价值是什么

经典的01背包只有一个限制:背包的体积

可以看出与经典的01背包不同，它有两个限制，一个是精灵球的数量，一个是皮卡丘的体力(这个题中可以剖析出来皮卡丘的体力不能为0,枚举体力时记得处理枚举边界)

dp思路：(仿照01背包)

状态表示：
	集合：f[i][j][u]表示的是从前i个精灵中选，权值1(体力v1[i])不能超过j权值2(球数v2[i])不能超过u的所有方案的集合
	属性：max(收集的精灵的数量的最大值)
状态转移：
		[1,2,3...,i,...,k]
	第i个精灵选与不选：
	不选：f[i][j][u] = f[i-1][j][u]
	选： if(j-v1[i] >= 0 && u-v2[i] >= 0) f[i][j][u] = max(f[i][j][u],f[i-1][j-v1[i]][u-v2[i]]+1) (体力和球的数量要足够)

代码

朴素版的内存超限了：

#include<iostream>
using namespace std;

const int N = 1010,M = 510;
int f[110][M][N];
int n,m,k; // 球数量，体力，精灵数量
int v1[110],v2[110]; // 体力v1,球数量v2

int main()
{
    cin >> n >> m >> k;
    for(int i = 1; i <= k;i ++) cin >> v2[i] >> v1[i];
    
    for(int i = 1;i <= k;i ++)
    {
        for(int j = 1;j < m; j ++)
        {
            for(int u = 1;u <= n; u ++)
            {
                f[i][j][u] = f[i-1][j][u];
                if(j-v1[i] >= 0 && u-v2[i] >= 0) f[i][j][u] = max(f[i][j][u],f[i-1][j-v1[i]][u-v2[i]]+1);
            }
        }
    }
    cout << f[k][m-1][n] << ' ';
    
    // 求收服这么多精灵时所消耗的最少体力
    int t = m;
    while(t > 0 && f[k][m-1][n] == f[k][t - 1][n]) t --;
    cout << m - t ; // 剩余体力就是m-t
    
    return 0;
}

优化版(仿照01背包优化)：

#include<iostream>
using namespace std;

const int N = 1010,M = 510;
int f[M][N];
int n,m,k; // 球数量，体力，精灵数量
int v1[110],v2[110]; // 体力v1,球数量v2

int main()
{
    cin >> n >> m >> k;
    for(int i = 1; i <= k;i ++) cin >> v2[i] >> v1[i];
    
    for(int i = 1;i <= k;i ++)
    {
        for(int j = m - 1;j >= v1[i]; j --)
        {
            for(int u = n;u >= v2[i]; u --)
            {
                f[j][u] = max(f[j][u],f[j-v1[i]][u-v2[i]]+1);
            }
        }
    }
    cout << f[m-1][n] << ' ';
    
    // 求收服这么多精灵时所消耗的最少体力
    int t = m;
    while(t > 0 && f[m-1][n] == f[t - 1][n]) t --;
    cout << m - t ; // 剩余体力就是m-t
    
    return 0;
}