分组背包习题题解（洛谷题单）

本篇对应源码见仓库 solutions/xcpc/algorithm/dp/knapsack-group/。

P1757 通天之分组背包

题意

分组背包的模板题。

思路

分组背包的模板题。

示例代码

signed main() {
    IOS;

    int m, n;
    cin >> m >> n;
    vector<vector<pii>> g(n + 1);

    int k = 1;
    fer(i, 0, n) {
    	int w, v, p;
    	cin >> w >> v >> p;
    	g[p].push_back({w, v});
    	k = max(k, p);
    }
    vector<ll> dp(m + 1);

    fer(i, 1, k + 1) {
    	ferd(j, m, 0) {
    		for(auto &[w, v] : g[i]) {
    			if(j >= w) {
    				dp[j] = max(dp[j], dp[j - w] + v);
    			}
    		}
    	}
    }
    cout << dp[m] << '\n';

    return 0;
}

P5322 BJOI2019 排兵布阵

题意

有 $n$ 座城堡，$s$ 名敌对玩家，所有玩家最多可以发配 $m$ 名士兵，如果一名玩家向第 $i$ 座城堡派遣的士兵数严格大于对手派遣士兵数的两倍，那么这名玩家就占领了这座城堡，获得 $i$ 分。现在小 $C$ 即将和其他 $s$ 名玩家两两对战，这 $s$ 场对决的派遣士兵方案必须相同。现在已得知了其他 $s$ 名玩家即将使用的策略，求小 $C$ 总分的最大值。

思路

将 $n$ 座城堡看成分组背包的 $n$ 组物品，玩家看成一组物品的小物品，士兵看成背包容量，那么：

g[i][k] 表示第 $k$ 个玩家在第 $i$ 座城堡派遣的士兵数。

• 状态定义： $dp[j]$ 表示发配士兵数量为 $j$ 时能获得的最大价值
• 遍历方式： 先遍历组数（每座城堡），在逆序遍历背包容量（士兵数量），最后遍历每组物品的小物品（每个城堡对应的每个玩家）
• 状态转移： if(j > 2 * g[i][k]) dp[j] = max(dp[j], dp[j - 2 * g[i][k] - 1] + k * i)，与普通分组背包不同点在于在状态转移的时候价值的计算方式不同。
• 注意，每个城堡的所有玩家派遣的士兵数需要排序，以保证状态转移时的正确性。

示例代码

signed main() {
    IOS;

    int s, n, m;
    cin >> s >> n >> m;
    vector<vector<int>> g(n + 1, vector<int>(s + 1));

    fer(i, 1, s + 1) {
    	fer(j, 1, n + 1) {
    		cin >> g[j][i];
    	}
    }
    fer(j, 1, n + 1) sort(all(g[j]));

    vector<int> dp(m + 1);

    fer(i, 1, n + 1) {
    	ferd(j, m, 0) {
    		fer(k, 1, s + 1) {
    			if(j > 2 * g[i][k]) {
    				dp[j] = max(dp[j], dp[j - 2 * g[i][k] - 1] + k * i);
    			}
    		}
    	}
    }
    cout << dp[m] << '\n';

    return 0;
}