最简单的背包问题，标题应该是除了背包测试中心：您无法打开二维数组。我还没有开的二维。光看数据是不可能的。

太大。

有两种方法来提高全省内存DP：

1 所谓卷的阵列

2 反向表

久没做背包DP，突然认为这样的背包问题非常easy了。

以下给出两种解法:

1 calBag()是滚动数组

2 calBag2()是逆向填表

#pragma once

#include <stdio.h>

#include <stdlib.h>

#include <vector>

using namespace std;

const int MAX_W = 12881;

const int MAX_N = 3403;

int N, M;//M是total weight

int wei[MAX_N];

int desi[MAX_N];

int tbl[MAX_W];

int calBag2()

{

	memset(tbl, 0, sizeof(int)*(M+1));

	for (int i = 1; i <= N; i++)

	{

		for (int j = M; j >= wei[i]; j--)

			tbl[j] = max(tbl[j], tbl[j-wei[i]]+desi[i]);

	}

	return tbl[M];

}

int calBag()

{

	vector<vector<int> > tbl(2, vector<int>(M+1));

	bool id = true;

	for (int i = 1; i <= N; i++)

	{

		for (int j = 1; j < wei[i] && j <= M; j++) tbl[id][j] = tbl[!id][j];

		for (int j = wei[i]; j <= M; j++)

		{

			tbl[id][j] = max(tbl[!id][j], tbl[!id][j-wei[i]]+desi[i]);

		}//注意都是上一列的数据往下拉,都是!id数列比較

		id = !id;

	}

	return tbl[!id][M];

}

int main()

{

	while (scanf("%d %d", &N, &M) != EOF)

	{

		for (int i = 1; i <= N; i++)

		{

			scanf("%d %d", &wei[i], &desi[i]);

		}

		printf("%d\n", calBag2());

	}

	return 0;

}