不优化貌似会tle 数据范围好像也不太对贡献了几个re 加一个判断条件就好

#include<string.h>
#include<stdio.h>
int s,n,max, a[111],x,y,z, i,k, j,v[100005];
int main() {
	while (scanf("%d", &s) != EOF)
	{
		memset(v, 0, sizeof(v)); v[0] = 1; z = 1;
		scanf("%d",&n);
		for (i = 1; i <= n; i++)
		{
			scanf("%d%d", &x, &y);
			k = 1;
			while (x>0)
			{if(x>=k) a[z++] = k*y, x = x - k, k = k<<1;
			else {
				a[z++] = x*y; break;
	}}}
		for (i = 1; i < z; i++)
			for (j = s; j >= 0; j--)
				if (v[j]&& j + a[i] <= s)
				 v[j + a[i]] = 1;
		for (i = s; i!=0; i--)
			if (v[i]) break;
		printf("%d\n",i);
	}}

• Re:背包水题 萌新的2进制优化模板 552K 47MS 536B (657) CcccccM 2018-04-26 19:14:21