算法提高课汇总

算法思路

理解题意

组合问题; 每个小精灵有两种选择: 收服/不收服 <--> 一个物品的两种选择; 问题的限制有两个,
所以问题可抽象为二维的$01$背包问题.

二维$01$背包

1. 限制
   • 收服小精灵需要精灵球
   • 需要皮卡丘的体力, 注意在收服过程中不能让皮卡丘的体力变成0: “使得皮卡丘体力小于等于0的野生小精灵也不会被小智收服”.
2. 目标
   • Max收集精灵的数目
   • 在此基础上皮卡丘的体力剩余最多. 计算最多剩余体力有两种方式:
     a) 不考虑剩余体力, 而在最多收服精灵个数的状态中找到对应皮卡丘剩余体力最小的状态
     b) 将体力也考虑为目标, 但这会将问题变复杂, 所以主要考虑a)方式.

下面用Y氏DP分析状态:

因为限制有2个, 所以相比$01$背包需要额外的一维表示额外的限制.

状态表示 $dp(i,j,k)$

• 集合: 在前$i$个小精灵中选择, 且精灵球数目不超过$j$, 体力消耗不超过$k$的所有选择

• 属性: Max收服精灵数目

状态计算

假设收服第$i$个小精灵需要精灵球$v1_i$个, 消耗皮卡丘$v2_i$点体力.

• 不收服, 对应集合最大值: $dp(i-1, j, k)$.

• 收服, 确定部分: 收服第$i$个精灵, 收服精灵数目$+1$, 精灵球数目和皮卡丘体力分别消耗$v1_i$, $v2_i$,
  对应剩余部分的集合的最大值: $dp(i-1, j-v1_i, k - v2_i)$.

为保持状态$dp(i,j,k)$的Max属性, $dp(i,j,k) = max( dp(i-1,j,k), dp(i-1,j-v1_i,k-v2_i) + 1)$, 其中
第二个子集可能由于限制不存在, 可对应 $\varnothing $, 值为$0$.

代码实现

#include <iostream>
#include <algorithm>

using namespace std;

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

int n, V1, V2; //V1, V2分别表示精灵球数量、皮卡丘初始的体力值
int v1[N], v2[N];
int dp[M][K];

int main()
{
    cin >> V1 >> V2 >> n;
    for( int i = 1; i <= n; i ++ )  cin >> v1[i] >> v2[i];

    for( int i = 1; i <= n; i ++ )
    {
        for( int j = V1; j >= v1[i]; j -- )
        {
            for( int k = V2 - 1; k >= v2[i]; k -- )
            {//所消耗体力不能等于V2, 皮卡丘剩余的体力>0
                dp[j][k] = max( dp[j][k], dp[j - v1[i]][k - v2[i]] + 1 );
            }
        }
    }

    cout << dp[V1][V2 - 1] << ' '; //精灵最多数目
    //ans:数目最多的状态中消耗体力最小的值
    int ans = V2 - 1;
    while( ans > 0 && dp[V1][ans-1] == dp[V1][V2 - 1] ) ans -- ; 
    cout << V2 - ans << endl;

    return 0;
}

这里再给出b)方式的代码, 相比更加复杂. 但这种思路反映了题目的一个要求:

“主要目标是收服尽可能多的野生小精灵；如果可以收服的小精灵数量一样，小智希望皮卡丘受到的伤害越小”.

具体体现在代码中:

• 如果收服数目可以增加, 则更新收服数目, 且体力消耗必须更新;

• 如果收服数目不变, 选择体力消耗更小的方案.

具体代码:

#include <iostream>
#include <algorithm>

#define x first
#define y second

using namespace std;

typedef pair<int, int> pii;

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

int n, V1, V2; //V1, V2分别表示精灵球数量、皮卡丘初始的体力值
int v1[N], v2[N];
pii dp[M][K]; //first:收服精灵数目; second: 消耗体力

int main()
{
    cin >> V1 >> V2 >> n;
    for( int i = 1; i <= n; i ++ )  cin >> v1[i] >> v2[i];

    for( int i = 1; i <= n; i ++ )
    {
        for( int j = V1; j >= v1[i]; j -- )
        {
            for( int k = V2 - 1; k >= v2[i]; k -- )
            {//所消耗体力不能等于V2, 皮卡丘剩余的体力>0
                if( dp[j][k].x < dp[j - v1[i]][k - v2[i]].x + 1 )
                {
                    dp[j][k].x = dp[j - v1[i]][k - v2[i]].x + 1;
                    dp[j][k].y = dp[j - v1[i]][k - v2[i]].y + v2[i]; //消耗体力
                }
                else if( dp[j][k].x == dp[j - v1[i]][k - v2[i]].x + 1 )
                {
                    dp[j][k].y = min( dp[j][k].y, dp[j - v1[i]][k - v2[i]].y + v2[i] );
                }
            }
        }
    }
    cout << dp[V1][V2 - 1].x << ' ' << V2 - dp[V1][V2 - 1].y << endl;

    return 0;
}