題目\(1\)
Description
一個學校舉行拔河比賽，所有的人被分成了兩組，每個人必須（且只能夠）在其中的一組，且兩個組內的所有人體重加起來盡可能地接近.
Input
第\(1\)行是一個\(n\)，表示參加拔河比賽的總人數，\(n<=100\)，接下來的n行表示第\(1\)到第\(n\)個人的體重，每個人的體重都是整數\((1<=weight<=450)\)。
Output
包含兩個整數：分別是兩個組的所有人的體重和，用一個空格隔開。注意如果這兩個數不相等，則請把小的放在前面輸出。
Sample Input 1
3
100 90 200Sample Output 1
190 200Hint
\(n<=100,1<=weight<=450\)
模型
\(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_{i=1}^Nw[i]\).
實際代碼中,還可以使用滾動數組來優化空間.
代碼
#include<bits/stdc++.h>
using namespace std;#define MaxN 105
#define Maxw 45005
int w[MaxN],N;
int F[Maxw];
int Tx=0;int main()
{cin>>N;for(int i=1;i<=N;i++){cin>>w[i];Tx+=w[i];}for(int i=1;i<=N;i++)for(int P=Tx;P;P--)if(P-w[i]>=0)F[P]=max(F[P],F[P-w[i]]+w[i]);cout<<F[Tx/2]<<" "<<Tx-F[Tx/2]<<endl;return 0;
}題目\(2\)
Description
一個學校舉行拔河比賽，所有的人被分成了兩組，每個人必須（且只能夠）在其中的一組，兩個隊伍的人數之差不能超過1，且兩個組內的所有人體重加起來盡可能地接近.
Input
第\(1\)行是一個\(n\)，表示參加拔河比賽的總人數，\(n<=100\)，接下來的n行表示第\(1\)到第\(n\)個人的體重，每個人的體重都是整數\((1<=weight<=450)\)。
Output
包含兩個整數：分別是兩個組的所有人的體重和，用一個空格隔開。注意如果這兩個數不相等，則請把小的放在前面輸出。
Sample Input 1
3
100 90 200Sample Output 1
190 200Hint
\(n<=100,1<=weight<=450\)
模型
\(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_{i=1}^Nw[i]\).
同樣可以采用滾動數組優化,還要注意初始化邊界.
#include<bits/stdc++.h>
using namespace std;
#define INF 0x3f
#define MaxN 105
#define Maxw 45005
int w[MaxN],N;
int F[MaxN][Maxw];
int Tx=0;int main()
{cin>>N;for(int i=1;i<=N;i++){cin>>w[i];Tx+=w[i];}memset(F,-INF,sizeof(F));for(int i=0;i<=Tx>>1;i++)F[0][i]=0;for(int i=1;i<=N;i++)for(int j=i;j>=1;j--)for(int P=Tx>>1;P>=w[i];P--)F[j][P]=max(F[j][P],F[j-1][P-w[i]]+w[i]);int Ans=F[N>>1][Tx>>1];if(N%2)Ans=max(Ans,F[(N>>1)+1][Tx>>1]); cout<<Ans<<" "<<Tx-Ans<<endl;return 0;
}還要注意,本題中第三重循環必須從\(Sum/2\)開始,即代碼中的
for(int P=Tx>>1;P>=w[i];P--)否則會超時.
)
