我用多重背包过的，但是看见很多大牛用%算法过的，不是很懂，有没有大牛能给个证明呢？？？不胜感激~~~并且在算法是加了个%30的，由700MS变为0MS了，但是不知道为什么。。。能有大牛解释一下吗？？？？
为什么%6会错，%12才AC呢？？？
#include<cstdio>
#include<cstring>
#define N 200010
bool vist[N];
int main()
{
	int a[10];
	int cont = 1;
	while(true)
	{
		for(int i = 1;i<=6;i++)
			scanf("%d",&a[i]);
		if(a[1]==0&&a[2]==0&&a[3]==0&&a[4]==0&&a[5]==0&&a[6]==0)
			break;
		
		vist[0] = true;
		int sum = 0;
		for(int i = 1;i<=6;i++)
		{
			a[i]%=30;////我在这里加了之前没有就700MS，有就0MS
			sum+=i*a[i];
		}
		
		printf("Collection #%d:\n",cont++);
		if(sum%2!=0)
		{
			printf("Can't be divided.\n\n");
			continue;
		}
		for(int i = 1;i<=sum;i++)
			vist[i] = false;
		for(int i = 1;i<=6;i++)
			if(a[i])
			for(int j = sum;j>=0;j--)
				if(vist[j])
					for(int k = 1;k<=a[i];k++)
					{
						if(j+k*i>sum)
							break;
						vist[j+k*i] = true;
						if(vist[sum/2])///////剪啊剪啊！！！！！！！
							goto end;
						//printf("%d\n",j+k*i);
					}
end:
		if(vist[sum/2])
			printf("Can be divided.\n");
		else
			printf("Can't be divided.\n");
		printf("\n");
	}
}

• Re:我在算法是加了个%30的，由700MS变为0MS了，但是不知道为什么。。。能有大牛解释一下吗？？？？？不胜感激~~~ (88) lgq1205 2009-08-15 01:12:44
  • Re:我在算法是加了个%30的，由700MS变为0MS了，但是不知道为什么。。。能有大牛解释一下吗？？？？？不胜感激~~~ (149) lolihunter 2009-09-04 22:48:26
    • Re:我在算法是加了个%30的，由700MS变为0MS了，但是不知道为什么。。。能有大牛解释一下吗？？？？？不胜感激~~~ (85) soarwind 2009-11-02 13:11:08