3597657_ac_250ms_284k.cpp

来自「北大大牛代码 1240道题的原代码 超级权威」· C++ 代码 · 共 50 行

#include <stdio.h>
#include <algorithm>

using namespace std;

struct node
{
	int w, d;
}charm[3410];

int best[12881];
int n, w;

int main()
{
	int i, j;

	scanf("%d%d", &n, &w);
	for (i = 0; i < n; i++)
	{
		scanf("%d%d", &charm[i].w, &charm[i].d);
	}
	memset(best, -1, sizeof(best));
	best[0] = 0;
	for (i = 0; i < n; i++)
	{
		for (j = w - charm[i].w; j >= 0; j--)
		{
			if (best[j] != -1)
			{
				int tw = j + charm[i].w;
				int td = best[j] + charm[i].d;
				if (best[tw] < td)
				{
					best[tw] = td;
				}
			}
		}
	}
	int ans = 0;
	for (i = 0; i <= w; i++)
	{
		if (best[i] > ans)
		{
			ans = best[i];
		}
	}
	printf("%d\n", ans);
	return 0;
}