宠物小精灵之收服

题目 宠物小精灵之收服

思路分析

加了一个维度限制的背包问题

要在k个精灵中选 有精灵球数量N和皮卡丘的体力M作为限制 要求得到的精灵数最多 若有相同情况 取剩余M更大的那个

代码实现

#include<bits/stdc++.h>

using namespace std;

const int N=1010,M=510,K=110;

int num[K],cost[N];

int f[N][M];

int main()

{

    int V1,V2,n;

    cin>>V1>>V2>>n;

    for(int i=1;i<=n;i++)

    {

        int v1,v2;

        cin>>v1>>v2;

        for(int j=V1;j>=v1;j--){

            for(int k=V2;k>=v2;k--){

                f[j][k]=max(f[j][k],f[j-v1][k-v2]+1);

            }

        }

    }

    cout<<f[V1][V2]<<" ";

    int k=V2;

    //反推得到最小体力消耗且达到最大值的

    while (k >= 0 && f[V1][k] == f[V1][V2])

        k--;

    cout<<V2-k-1;

    return 0;

}

同类题型

视频讲解

⬅️ 加维度背包问题练习 🏠 00-刷题理模型 ➡️ 有依赖+多重（未解决）金明的预算方案