荔园在线
荔园之美，在春之萌芽，在夏之绽放，在秋之收获，在冬之沉淀
[回到开始]
[上一篇][下一篇]
发信人: hsfzer (NoName), 信区: ACMICPC
标 题: 解题随笔：UVA 562 Dividing Coins (陈伟坚)
发信站: 荔园晨风BBS站 (Sun Oct 18 17:19:07 2009), 站内
解题随笔：UVA 562 Dividing Coins (陈伟坚)
题目大意：将一堆不同面值的硬币，尽量平均地分给两个人，也就是，找到一种分法，使得
两堆硬币的面值之和最小。
思路：刚开始，拿到题目的时候，有点茫然。细想了一下，原来是一道简单的01背包的题目
。首先，将所有硬币的面值加起来，得到一个值SUM。然后，以SUM的一半，也就是（SUM/2
）作为背包的总容量。计算在(SUM/2)的总容量下，能取到得硬币的总面值，设为TMP。那么
最后结果ANS=SUM-TMP-TMP。
描述性证明如下：设分成的两堆硬币总面值分别为A,B.不妨设A<=B.由于A+B=SUM。那么有
A<=(SUM/2).为了使ANS(=B-A)的值最小，那么A应该尽量地大(因为A+B=SUM是定值)。在
A<=(SUM/2)的情况下，使A尽量大，这是一个典型的01背包问题。
#include <stdio.h>
#include <memory.h>
int n,coin[100];
int dp[100][30000];
int dfs(int pos,int w);
int main()
{
int t,i;
int sum,tmp,ans;
scanf("%d",&t);
while (t--)
{
scanf("%d",&n);
sum=0;
for (i=0;i<n;i++)
{
scanf("%d",&coin[i]);
sum+=coin[i];
}
memset(dp,-1,sizeof(dp));
tmp=dfs(0,sum/2);
ans=sum-tmp-tmp;
printf("%d\n",ans);
}
return 0;
}
int dfs(int pos,int w)
{
int tmp;
if (pos==n)return 0;
if (dp[pos][w]!=-1)return dp[pos][w];
tmp=dfs(pos+1,w);
if (w-coin[pos]>=0&&tmp<dfs(pos+1,w-coin[pos])+coin[pos])
tmp=dfs(pos+1,w-coin[pos])+coin[pos];
dp[pos][w]=tmp;
return dp[pos][w];
}
--
※ 来源:·荔园晨风BBS站 http://bbs.szu.edu.cn·[FROM: 192.168.14.29]
[回到开始]
[上一篇][下一篇]
荔园在线首页 友情链接：深圳大学 深大招生 荔园晨风BBS S-Term软件 网络书店