Big Event in HDU(항 전 1171)(다 중 가방)와(모 함수)두 가지 해법

   
     

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

   
     

      
    20 10
40 40
   
     
   
     

      
    //    ：
   
     
   
     

    
      
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
int dp[100000],sum,ans;
struct st
{
	int v;
	int m;
}data[100000];
void full(int x)
{
	for(int i=data[x].v;i<=ans;i++)
	dp[i]=max(dp[i],dp[i-data[x].v]+data[x].v);
}
void one(int x)
{
	for(int j=1;j<=data[x].m;j++)
	     for(int i=ans;i>=data[x].v;i--)
	         dp[i]=max(dp[i],dp[i-data[x].v]+data[x].v);
}
int main()
{
	int i,j,n;
	while(scanf("%d",&n)&&(n>0))
	{
		memset(dp,0,sizeof(dp));
		sum=0;
		for(i=1;i<=n;i++)
		{
			scanf("%d%d",&data[i].v,&data[i].m);
			sum+=data[i].v*data[i].m;
		}
		ans=sum/2;
		for(i=1;i<=n;i++)
		{
			if(data[i].v*data[i].m>=ans)
			full(i);
			else
			one(i);
		}
		printf("%d %d
",sum-dp[ans],dp[ans]);
	}
	return 0;
}
 
//     ：
 
/*     a,s  ，WA    ，      。。  。 
*/
#include<stdio.h>
#include<string.h>
int a[250010],s[250010];
int v[55],m[55]; 
int main()
{
	int n,i,j,k,sum,ans;
	while(scanf("%d",&n)&&n>0)
	{
		sum=0;
		memset(s,0,sizeof(s));
		memset(a,0,sizeof(a));
		for(i=1;i<=n;i++)
		{
			scanf("%d%d",&v[i],&m[i]);
			sum+=v[i]*m[i];
		}
		for(i=0;i<=v[1]*m[1];i+=v[1])//    。 
		{
			s[i]=1;
		}
		for(i=2;i<=n;i++)
		{
			for(j=0;j<=sum;j++)
			{
		      	for(k=0;k+j<=sum&&k<=v[i]*m[i];k+=v[i])
				{
				   a[k+j]+=s[j];
			    }
			}
			for(k=0;k<=sum;k++)
			{
				s[k]=a[k];
				a[k]=0;
			}
		}
		for(i=sum/2;i>=0;i--)
		{
			if(s[i])
			{
			    printf("%d %d
",sum-i,i);
			    break;
			}
		}
	}
	return 0;
}