UVA10482 The Candyman Can
思路
记总重量为 \(sum\)。因为 \(n\le 32\) 所以可以暴力。使用动态规划，\(dp_{i,j}\) 代表第 \(1\) 组重量为 \(i\)，第 \(2\) 组重量为 \(j\)（则第 \(3\) 组重量为 \(sum-i-j\)）是否可以达到。最后再暴力枚举取所有 \(\max (i,j,sum-i-j)- \min (i,j,sum-i-j)\) 中的最小值即为答案。
AC 代码
#include<bits/stdc++.h>
using namespace std;
#define N 2005
long long t,tt,n,a[N],sum,mn,dp[N][N];
int main(){
cin>>t;
tt=t;
while(t--){
mn=1e9,sum=0;
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i],sum+=a[i];
memset(dp,0,sizeof(dp));
dp[0][0]=1;
for(int i=1;i<=n;i++){
for(int j=sum;j>=0;j--){
for(int k=sum-j;k>=0;k--){
if(dp[j][k]){//若dp[j][k]可以达到
dp[j+a[i]][k]=dp[j][k];//则dp[j+a[i]][k]和dp[j][k+a[i]]也可以
dp[j][k+a[i]]=dp[j][k];
}
}
}
}
for(int j=sum;j>=0;j--){
for(int k=sum-j;k>=0;k--){
if(dp[j][k]) mn=min(mn,max({(long long)j,(long long)k,sum-j-k})-min({(long long)j,(long long)k,sum-j-k}));
}
}
cout<<"Case "<<tt-t<<": "<<mn<<endl;
}
return 0;
}