【HDU 1171】【バックパックDPまたは母関数】Big Event in HDU【nのようなものがあります.それぞれの商品の価値はvで、件数はmです.これらのものを二つに分けて、両方の価値が一番近いようにします.】

転送ゲート:http://acm.split.hdu.edu.cn/showproblem.php?pid=1171
説明:
Big Event in HDU
Time Limit:10000/5000 MS(Java/Others)    メモリLimit:65536/32768 K(Java/Others)Total Submission(s):36806    Acceepted Submission(s):12727
Problem Description
Nowadays,we all know that Coputer Collage is the bigget department in HDU.But,maybore you don't know that Coput Collage had ever been split into Coput Collage and Software Collage 2002.
The spliting is absolutiely a big event in HDU!At the same time,it is a trouble thing too.All facilitys must go halves.First,all facilityes ares assess,and two facilitys are thought to be same the same value.It is assisted ththe is is
 
Input
Input contains multiple test cases.Each test case starts with a number N(0<=N==50--the total number of different facilitys).The next N integer V(0 A test case starting with a negative intetens inative.inites.intetetetetens
 
Output
For each case,print one line containing two integers A and B which denote the value of Computter Collage and Software Collage will get rectively.A and B shoud be as equal as possible.At the same time me.At the same time me me me me me me me.shatyou.
 
Sample Input

 
   

     2 10 1 20 1 3 10 1 20 2 30 1 -1 
   
 
  

题意：

有n样物品，每样物品价值是v，件数是m。尽量把这些物品分成两堆使得两边总价值最接近。输出分得的两堆各自的价值。

思路一（多重背包）：

因为题目要求要尽量平均分配，所以我们可以先将总价值sum求出，然后得出其分配的平均值为sum/2,要注意这个答案可能为小数，但是又因为sum是整数，所以最后得出的sum/2是要小于等于实际的值。将这个结果进行01,背包，可以得出其中一个宿舍所得的最大价值，而另一个宿舍的最大价值也可以相应的得到，而前者必定小于等于后者。

01背包专题可以见Here

代码一：

#include
using  namespace std;

int val[5005];
int dp[255555];

int  main(){
  int n,sum,cnt;
  while(~scanf("%d",&n),n>0){
    memset(val, 0, sizeof(val));
    memset(dp, 0, sizeof(dp));
    sum=0;cnt=0;
    int a,b;
    for(int i=1; i<=n; i++){
      scanf("%d%d",&a,&b);
      while(b--){
        val[cnt++]=a;//       
        sum+=a;
      }
    }
    for(int i=0; i=val[i]; j--){  //01  
        dp[j]=max(dp[j], dp[j-val[i]]+val[i]);
      }
    }
    printf("%d %d
",sum-dp[sum/2],dp[sum/2]);
  }
  return 0;
}

構想二(母関数):
HDU 1085のやり方と似ています.
母関数法を利用して解決します.二つの山に分けて、二つの中の小さい一山は全部の物の価値量の半分になります.母関数の組み合わせは上から下まで全部の価値量の半分に設定できます.すべての組み合わせを求めたら、欲張りな思想で答えを得ることができます.二つの山の差ができるだけ小さいため、総価値量の半分からできます.小さい方向に探し始めました.最大の価値量を見つけたら、もう一つの山の価値量は総価値量です.この山の価値量です.組み合わせが大きいかもしれないので、ここでは組み合わせの種類を記録しないで、一つのマークでこの数が組み合わせるかどうかを表します.
コード二:

#include 
#include 
#include 
#include 
#include 
using namespace std;

#define N 1000000
int c1[N];
int c2[N];
int a[N]; //    
int b[N];  //    

int main(){
  int n,i,j,k;
  while(scanf("%d",&n), n > 0) {
    int sum=0;
    for(i=0;i=0;i--) {
      if(c1[i]!=0) break;
    }
    printf("%d %d
",sum-i,i);
  }
  return 0;
}