UVA 562 Dividing coins

题目描述：给出一些不同面值的硬币，每个硬币只有一个。将这些硬币分成两堆，并且两堆硬币的面值和尽可能接近。

分析：将所有能够取到的面值数标记出来，然后选择最接近sum/2的两个面值

状态表示:d[j]表示用当前给定的硬币是否可以凑得总面值j

转移方程：d[j]=d[ j-coin[i] ]

开始时只取出硬币coin[0]，判断它是否能凑得总面值j

每新加入一个硬币coin[i]时，判断所有已经取出的硬币能否凑得总面值j

 #include <iostream>

 #include <cstdio>

 #include <string.h>

 #include <cmath>

 #include <algorithm>

 using namespace std;

 bool dp[];

 int coin[];

 int n,sum;

 int main()

 {

     int t,i,j;

     scanf("%d",&t);

     while( t--)

     {

         scanf("%d",&n);

         sum =;

         for( i=; i<n; i++)

         {

             scanf("%d",&coin[i]);

             sum+= coin[i];

         }

         memset( dp,, sizeof( dp));

         dp[]=;

         for( i=; i<n; i++)

             for( j=sum;j>=coin[i]; j--)

                 if( !dp[j]) dp[j] =dp[j-coin[i]];

         for( i=sum/; i>=;i--)

             if( dp[i])

             {

                 printf("%d\n",sum-i-i);

                 break;

             }

     }

     return ;

 }

巴特西

UVA 562 Dividing coins

最新文章

热门文章