队伍配置(背包dp)

题目：

给n个人物m个装备，d是最大花费。每个人物和装备都有一个攻击力a和花费b。满足如下条件情况下选出一些人物和装备得到最大的攻击力：
（1）人物数量>=装备数量
（2）人物花费+装备花费<=d
（3）人物数量<=5
数据范围：0<n,m≤300，25≤d≤138，1000≤a1≤15488，500≤a2≤2500，3≤b1,b2≤12

做法：

01背包变形。这个数据范围即使没有第三个限制也能做。
思路是这样的：
dp1[j][k]表示选出≤j件装备花费≤k时，最大攻击力和。
dp2[j][k]表示选出j个人物花费≤k时，最大攻击力和。
如果我们得到上面信息。那么答案for一遍统计就好了：

for (int j = 1; j <= min(n, 5); ++j){
    for (int k = 0; k <= d; ++k){
        if (dp2[j][k] != -1) ans = max(ans, dp2[j][k]+dp1[j][d-k]);
    }
}

而dp1、dp2做2次背包dp即可。
转移：

代码：

#include <bits/stdc++.h>
#define debug(a) cout << #a ": " << a << endl
#define IOS ios::sync_with_stdio(false), cin.tie(0)
using namespace std;
typedef long long ll;
const int N = 310;
int n, m, sum;
struct node{
    int power, cost;
}guy[N], tool[N];
int dp1[N][N], dp2[N][N];
int main(void){
    IOS;
    cin >> n >> m >> sum;
    for (int i = 1; i <= n; ++i){
        cin >> guy[i].power >> guy[i].cost;
    }
    for (int i = 1; i <= m; ++i){
        cin >> tool[i].power >> tool[i].cost;
    }
    for (int i = 1; i <= m; ++i){
        for (int j = i; j >= 1; --j){
            for (int k = sum; k >= 0; --k){
                dp1[j][k] = max(dp1[j][k], dp1[j-1][k]);
                if (k >= tool[i].cost) dp1[j][k] = max(dp1[j][k], dp1[j-1][k-tool[i].cost]+tool[i].power);
            }
        }
    }
    memset(dp2, -1, sizeof dp2);
    for (int i = 0; i <= sum; ++i) dp2[0][i] = 0;
    for (int i = 1; i <= n; ++i){
        for (int j = i; j >= 1; --j){
            for (int k = sum; k >= guy[i].cost; --k){
                if (dp2[j-1][k-guy[i].cost] != -1) dp2[j][k] = max(dp2[j][k], dp2[j-1][k-guy[i].cost]+guy[i].power);
            }
        }
    }
    int ans = 0;
    for (int i = 1; i <= min(n, 5); ++i){
        for (int j = 0; j <= sum; ++j){
            if (dp2[i][j] == -1) continue;
            ans = max(ans, dp2[i][j]+dp1[min(i, m)][sum-j]);
        }
    }
    cout << ans << endl;
    return 0;
}