长沙做网站建设公司哪家好,免费网站建设创意,龙华住房和建设局网站,郴州新网招聘手机版题目\(1\) Description 一个学校举行拔河比赛#xff0c;所有的人被分成了两组#xff0c;每个人必须#xff08;且只能够#xff09;在其中的一组#xff0c;且两个组内的所有人体重加起来尽可能地接近. Input 第\(1\)行是一个\(n\)#xff0c;表示参加拔河比赛的总人数… 题目\(1\) Description 一个学校举行拔河比赛所有的人被分成了两组每个人必须且只能够在其中的一组且两个组内的所有人体重加起来尽可能地接近. Input 第\(1\)行是一个\(n\)表示参加拔河比赛的总人数\(n100\)接下来的n行表示第\(1\)到第\(n\)个人的体重每个人的体重都是整数\((1weight450)\)。 Output 包含两个整数分别是两个组的所有人的体重和用一个空格隔开。注意如果这两个数不相等则请把小的放在前面输出。 Sample Input 1 3
100 90 200 Sample Output 1 190 200 Hint \(n100,1weight450\) 模型 \(0-1\)背包 解法 转换成成一个花费\(\)价值的\(0-1\)背包问题,记\(F[i][j]\)为用前\(i\)个物品,总代价\(j\)能取得的最大价值,可得状态转移方程:\[F[i][j]max(F[i][j],F[i][j]-w[i]]w[i])\] 最后答案即为\(F[N][Sum/2]\),其中\(Sum\sum_{i1}^Nw[i]\). 实际代码中,还可以使用滚动数组来优化空间. 代码 #includebits/stdc.h
using namespace std;#define MaxN 105
#define Maxw 45005
int w[MaxN],N;
int F[Maxw];
int Tx0;int main()
{cinN;for(int i1;iN;i){cinw[i];Txw[i];}for(int i1;iN;i)for(int PTx;P;P--)if(P-w[i]0)F[P]max(F[P],F[P-w[i]]w[i]);coutF[Tx/2] Tx-F[Tx/2]endl;return 0;
} 题目\(2\) Description 一个学校举行拔河比赛所有的人被分成了两组每个人必须且只能够在其中的一组两个队伍的人数之差不能超过1且两个组内的所有人体重加起来尽可能地接近. Input 第\(1\)行是一个\(n\)表示参加拔河比赛的总人数\(n100\)接下来的n行表示第\(1\)到第\(n\)个人的体重每个人的体重都是整数\((1weight450)\)。 Output 包含两个整数分别是两个组的所有人的体重和用一个空格隔开。注意如果这两个数不相等则请把小的放在前面输出。 Sample Input 1 3
100 90 200 Sample Output 1 190 200 Hint \(n100,1weight450\) 模型 \(0-1\)背包 解法 同样转换成成一个花费\(\)价值的\(0-1\)背包问题,记\(F[i][j][k]\)为在前\(i\)个物品中选择\(k\)个,总代价\(j\)能取得的最大价值.可得状态转移方程:\[F[i][j][k]max(F[i][j][k],F[i-1][j-1][k-w[i]]w[i])\] 最终答案即为\(F[N][N/2][Sum]\),其中\(Sum\sum_{i1}^Nw[i]\). 同样可以采用滚动数组优化,还要注意初始化边界. #includebits/stdc.h
using namespace std;
#define INF 0x3f
#define MaxN 105
#define Maxw 45005
int w[MaxN],N;
int F[MaxN][Maxw];
int Tx0;int main()
{cinN;for(int i1;iN;i){cinw[i];Txw[i];}memset(F,-INF,sizeof(F));for(int i0;iTx1;i)F[0][i]0;for(int i1;iN;i)for(int ji;j1;j--)for(int PTx1;Pw[i];P--)F[j][P]max(F[j][P],F[j-1][P-w[i]]w[i]);int AnsF[N1][Tx1];if(N%2)Ansmax(Ans,F[(N1)1][Tx1]); coutAns Tx-Ansendl;return 0;
} 还要注意,本题中第三重循环必须从\(Sum/2\)开始,即代码中的 for(int PTx1;Pw[i];P--) 否则会超时. 转载于:https://www.cnblogs.com/TaylorSwift13/p/11172401.html
