2525 - 石子称量
时间限制 : 3 秒
内存限制 : 32 MB
现有一天平和N粒小石子，每粒石子质量记为Mi(1<=i<=N)，将其分成两堆。由于天平能够承载的倾斜程度有限，处于安全考虑，尽量使石子放在天平之后，天平倾斜角度最小。
求取天平偏角最小时，天平左盘可能放置的石子总质量。
题目输入
每组包含两行，
第一行输入N(0<N<500)，
第二行输入N颗石子的质量Mi(0<i<=N,0<Mi<20,Mi为整数)。
题目输出
每行输出天平左盘可能放置的石子总质量。(升序输出)
输入/输出样例
输入格式
3 1 2 4 5 1 1 1 1 1
输出格式
3 4 2 3
C语言解答
#include"stdio.h" #include"string.h" int dp[10001]; int max(int a,int b) { return a>b?a:b; } int main() { int n; while(scanf("%d",&n)!=EOF) { int s[501],i,j,sum=0; memset(dp,0,sizeof(dp)); for(i=0;i<n;i++) { scanf("%d",&s[i]); sum+=s[i]; } int v=sum/2; for(i=0;i<n;i++) for(j=v;j>=s[i];j--) dp[j]=max(dp[j],dp[j-s[i]]+s[i]); if(dp[v]!=sum-dp[v]) printf("%d %d\n",dp[v],sum-dp[v]); else printf("%d\n",dp[v]); } return 0; }
C++解答
#include <stdio.h> #define max(a,b) a>b?a:b int V,ans,n,w[21],sum[21]; void dfs(int i,int cnt) { if(i == 0) { ans = max(ans,cnt); return ; } if(ans == V || cnt+sum[i] <= ans) //cut return ; if(cnt+w[i] <= V) dfs(i-1,cnt+w[i]); dfs(i-1,cnt); } int main() { while(~scanf("%d",&n)) { ans = 0; for(int i=1;i<=n;i++) { scanf("%d",&w[i]); sum[i] = sum[i-1] + w[i]; } V = sum[n]/2; dfs(n,0); if (2*ans<sum[n])printf("%d %d\n",ans,sum[n]-ans); else printf("%d\n",ans); } return 0; }