题目里的数据能过，可总是WA，提交很多次了


#define max(a,b) a > b ? a : b
#include <cstdio>
#include <cstdlib>
#include <memory.h>
int f[100002];
int cash, kinds; 
int cost[12], weight[12], num[12];
int maxk(int n)
{
	int k = 1;
	int count = 0;
	while(k < n)
	{
		k *= 2;
		++count;
	}
	return count ;
}

int main()
{
	int i,j,k;
	int amount;
	while(scanf("%d", &cash) != EOF)
	{
		memset(f,0,sizeof(f));
		scanf("%d", &kinds);
		for(i = 1;  i <= kinds; ++i)
			scanf("%d%d", num + i, cost + i);
		for(i = 1; i <= kinds; ++i)
		{
			if(num[i] * cost[i] >= cash)
			{
				for(j = cost[i]; j <= cash; ++j)
					f[j] = max(f[j], f[j - cost[i]] + cost[i]);
			}
			else
			{
				k = 1;
				amount  = num[i];
				while(k < maxk(num[i]))
				{
					for(j = cash; j >= k * cost[i]; --j)
						f[j] = max(f[j], f[j - k * cost[i]] + k * cost[i]);
					amount -= k;
					k *= 2;
				}
				for(j = cash; j >= amount * cost[i]; --j)
					f[j] = max(f[j], f[j - amount * cost[i]] + amount * cost[i]);
			}
		}
		printf("%d\n",f[cash]);
	}
	return 0;
}

• Re:谁能帮我找错？ (1210) pangmm 2010-08-18 16:05:44
  • Re:谁能帮我找错？ (34) 1030202872 2010-10-22 18:16:39