我的源代码:
#include <stdio.h>
#include <string.h>
int max(int x,int y )
{return x>y?x:y;}
int d[125009];
void compete(int sum,int v,int w)
{
int i;
for(i=v;i<=sum;i++)
d[i]=max(d[i],d[i-v]+w);
}
void zero (int sum,int v,int w)
{
int i;
for(i=sum;i>=v;i--)
d[i]=max(d[i],d[i-v]+w);
}
int main()
{
int n,sum,l,k,v[52],m[52];
while(scanf("%d",&n)!=EOF&&n>0)
{
sum=0; memset(d,0,sizeof(d));
for(int i=1;i<=n;i++)
{
scanf("%d%d",&v[i],&m[i]);
sum+=v[i]*m[i];
}
int sum1=sum/2;
for(i=1;i<=n;i++)
{
if(v[i]*m[i]>=sum1)
compete(sum1,v[i],v[i]);
else
{
for(k=1,l=m[i];k<l;l-=k)
{
zero(sum1,k*v[i],k*v[i]);
k*=2;
}
zero(sum1,l*v[i],l*v[i]);
}
}
printf("%d %d\n",sum-d[sum1],d[sum1]);
}
return 0;
}
另外想问一下 ACCESS_VIOLATION 通常是什么情况导致的,除了数组越界
求解~~~~~
#include <stdio.h>
#include <string.h>
int max(int x,int y )
{return x>y?x:y;}
int d[125009];
void compete(int sum,int v,int w)
{
int i;
for(i=v;i<=sum;i++)
d[i]=max(d[i],d[i-v]+w);
}
void zero (int sum,int v,int w)
{
int i;
for(i=sum;i>=v;i--)
d[i]=max(d[i],d[i-v]+w);
}
int main()
{
int n,sum,l,k,v[52],m[52];
while(scanf("%d",&n)!=EOF&&n>0)
{
sum=0; memset(d,0,sizeof(d));
for(int i=1;i<=n;i++)
{
scanf("%d%d",&v[i],&m[i]);
sum+=v[i]*m[i];
}
int sum1=sum/2;
for(i=1;i<=n;i++)
{
if(v[i]*m[i]>=sum1)
compete(sum1,v[i],v[i]);
else
{
for(k=1,l=m[i];k<l;l-=k)
{
zero(sum1,k*v[i],k*v[i]);
k*=2;
}
zero(sum1,l*v[i],l*v[i]);
}
}
printf("%d %d\n",sum-d[sum1],d[sum1]);
}
return 0;
}
另外想问一下 ACCESS_VIOLATION 通常是什么情况导致的,除了数组越界
求解~~~~~