题解 P2663 【越越的组队】

看到：并要求这些同学综合能力测试的成绩之和在**不超过班级总分一半的前提下尽量达到最高**.这句话，第一反应是背包。 ------------ 进一步挖掘，输入只有一列所谓的**重量或价值**，自然而然的又想到是重量与价格同体的01背包。 ------------ ``` #include<cstdio> #include<cmath> using namespace std; int a[101],f[10001];//别被第一个括号中的范围迷惑,f数组记录的范围不止。要想知道，请您接着往下看 int main() { int n; scanf("%d",&n); int sum=0;//清零，为累计和做准备 for(int i=1;i<=n;i++) { scanf("%d",&a[i]); sum+=a[i];//本人较懒，直接跟着输入累计 } sum=sum/2;//不超过一半 int ans=0;//清零，为最大值准备 for(int i=1;i<=n;i++) { for(int j=sum;j>=a[i];j--)//还记的f数组的范围吗？这就是答案 {//以上两行for是经典01背包，在这里不在加以说明，想得到细致讲解，请私信我 int x=fmax(f[j],f[j-a[i]]+a[i]);//大家接着往下看几行，会发现先记录一下省了两次，节约一丁点时间 if(x<=sum)//别忘了必须小于(题目要求)，因为已经不是a[i]了。 { f[j]=x;//01背包 ans=fmax(ans,f[j]);//话说这就是要求最终的最大值 } } } printf("%d",ans); return 0; } ``` 蒟蒻尽力做到精细讲解，希望大家能接收。 求过