hdu1171 参考答案

   1 /*
   2 hdu1171 经典DP:集合划分成两个子集，总和相差最小
   3 ymc 2008/9/25
   4 题目大意：
   5 给定n种设备，每种设备有数量num[i],价值v[i]。
   6 把这n种设备分成两部分，使得这两部分的价值相差最小。
   7 差最小。
   8 分析与解题思路
   9 参考zju1366。
  10 令ans[i][j]表示用前i种设备中选若干个设备，总价值不超过j的最大价值。
  11 则ans[i][j]可能含有k个第i种设备，其中0<=k<=num[i],并且k*v[i]<=j。
  12 有状态转移方程
  13 ans[i][j]=max{ans[i-1][j-k*v[i]]+k*v[i]}。
  14 实现的时候从低向上求。
  15 */
  16 #include <iostream>
  17 using namespace std;
  18 const int N=51;
  19 const int Max=100000;
  20 int v[N];
  21 int num[N];
  22 int n;
  23 int ans[N][Max];
  24 void DP(int value)
  25 {
  26     memset(ans,0,sizeof(ans));
  27     int t;
  28     for(int i=1;i<=n;i++)
  29         for(int j=1;j<=value;j++)
  30             for(int k=0;k<=num[i];k++)
  31             {
  32                 t=j-k*v[i];
  33                 if(t<0)
  34                     break;
  35                 if(ans[i-1][t]+k*v[i]>ans[i][j])
  36                     ans[i][j]=ans[i-1][t]+k*v[i];
  37             }
  38 
  39 }
  40 int main()
  41 {
  42     int sum;
  43     while(1)
  44     {
  45         scanf("%d",&n);
  46         if(n<0)
  47             break;
  48         sum=0;
  49         for(int i=1;i<=n;i++)
  50         {
  51             scanf("%d %d",&v[i],&num[i]);
  52             sum+=v[i]*num[i];
  53         }
  54         DP(sum/2);
  55         printf("%d %d\n",sum-ans[n][sum/2],ans[n][sum/2]);
  56     }
  57 }