HDu 1059 Dividing--DP-多重リュックサック問題

/*
	      
	               
	                     
	       ：                    （       1，        ）
*/
#include<stdio.h>
#include<string.h>
int d[120000],n[7],w;
void cpack(int c,int ww)
{
	int j;
	for(j=c;j<=w;j++)
	{
		if((d[j-c]+ww)>d[j])
			d[j]=d[j-c]+ww;
	}
}
void znpack(int c,int ww)
{
	int j;
	for(j=w;j>=c;j--)
	{	
		if(d[j]<(d[j-c]+ww))
			d[j]=d[j-c]+ww;
	}
}
void mpack(int c,int ww,int nn)
{
	
	if(c*nn>=w)
	{
		cpack(c,ww);
		return;
	}
	int k=1;
	while(k<nn)
	{
		znpack(k*c,k*ww);
		nn=nn-k;
		k=k*2;
	}
	znpack(nn*c,nn*ww);
}
int main()
{
	int q=1,i;
	while(1)
	{
		w=0;
		for(i=1;i<=6;i++)
		{
			scanf("%d",&n[i]);
			w+=i*n[i];
		}
		if(!w)
			break;
		if(w%2)
		{
			printf("Collection #%d:
Can't be divided.

",q++);
			continue;
		}
		w=w/2;
		d[0]=0;
		memset(d,0,sizeof(d));
		for(i=1;i<=6;i++)
		{
			if(!n[i])
				continue;
			mpack(i,i,n[i]);
		}
		if(d[w]!=w)
			printf("Collection #%d:
Can't be divided.

",q++);
		else printf("Collection #%d:
Can be divided.

",q++);
	}
	return 0;
}

以上は私が他人の真似をして、私はもともと自分で書いた配列が小さくなったため、システムはRuntime Error(ACCESS_VIOLATION)をあげて、同時にボールの消耗する空間をそれと同じ価値と仮定していないので、求めるしかありません:総数の半分の価値を占めて、最大(または最小、最小は配列を正無限に初期化することができ、データが合法かどうかを判断する必要はありません)でいくつかのボールを得ることができます.d[一般価値]=初期化では、分割できません.そのため、処理は複雑です.

#include<stdio.h>
int d[120000],n[7],w;
void cpack(int c,int ww)
{
    int j;
    for(j=c;j<=w;j++)
    {
        if((d[j-c]+ww)<d[j])
            d[j]=d[j-c]+ww;
    }
}
void znpack(int c,int ww)
{
    int j;
    for(j=w;j>=c;j--)
    {    
        if(d[j]>(d[j-c]+ww))
            d[j]=d[j-c]+ww;
    }
}
void mpack(int c,int ww,int nn)
{
    
    if(c*nn>=w)
    {
        cpack(c,ww);
        return;
    }
    int k=1;
    while(k<nn)
    {
        znpack(k*c,k*ww);
        nn=nn-k;
        k=k*2;
    }
    znpack(nn*c,nn*ww);
}
int main()
{
    int q=1,i;
    while(1)
    {
        w=0;
        for(i=1;i<=6;i++)
        {
            scanf("%d",&n[i]);
            w+=i*n[i];
        }
        if(!w)
            break;
        if(w%2)
        {
            printf("Collection #%d:
Can't be divided.

",q++);
            continue;
        }
        w=w/2;
        d[0]=0;
        for(i=1;i<=w;i++)
            d[i]=999999999;
        for(i=1;i<=6;i++)
            mpack(i,1,n[i]);
        if(d[w]==999999999)
            printf("Collection #%d:
Can't be divided.

",q++);
        else printf("Collection #%d:
Can be divided.

",q++);
    }
    return 0;
}