题目链接
洛谷 P2663 越越的组队
思路分析
一道 0-1 背包变种。
由于它规定必须取正好 \(\dfrac{n}{2}\) 个人的成绩，所以不能用多维背包。考虑规定布尔型数组 \(dp_{i,j}\) 表示选 \(i\) 个人能否使成绩总和为 \(j\)。则状态转移方程即为 \(dp_{i,j}=dp_{i,j} \lor dp_{i-1,j-a_i}\)，其中 \(dp_{0,0}=true\)。
代码呈现
#include<bits/stdc++.h>
using namespace std;const int N=105,M=10010;
int n;
int a[N];
bool dp[N][M];int main(){scanf("%d",&n);for (int i=1;i<=n;++i) scanf("%d",a+i);int s=0;for (int i=1;i<=n;++i) s+=a[i];dp[0][0]=1;for (int i=1;i<=n;++i){for (int j=i;j>=1;--j){for (int k=s/2;k>=a[i];--k) dp[j][k]|=dp[j-1][k-a[i]];}}for (int i=s/2;i>=0;--i){if (dp[n/2][i]){ printf("%d",i);break; }}return 0;
}