#include<iostream>
#include<algorithm>
using namespace std;
int N, M;            //N个物品，包的体积为M
int w[3505], d[3505];      //体积，价值
int result[13005];         //result[i]表示从从 某些物品 中取出体积为i的最大价值
int main()
{
	scanf("%d%d", &N, &M);
//	cin >> N >> M;
	for (int i = 1; i <= N; ++i)
	{
		scanf("%d%d", &w[i], &d[i]);
	//	cin >> w[i] >> d[i];
	}
	result[0] = 0;             //取体积为0，价值为0      

	for (int j = 1; j <= M; ++j)            //result数组初始化为从第1个物品中取 体积为j 的最大价值，此后不断更新
		if (w[1] > j)
			result[j] = 0;
		else
			result[j] = d[1];

	for (int i = 2; i < N; ++i)            //从前i个物品取体积为j
		for (int j = M; j >= 1; --j)
		{
			if (j >= w[i])          //第i个物品可以取的话，尝试更新
			    result[j] = max(result[j], result[j - w[i]] + d[i]);
		}
	if (M > w[N])
		result[M] = max(result[M], result[M - w[N]] + d[N]);
//	cout << result[M] << endl;
	printf("%d\n", result[M]);
	return 0;
}

• ！ (514) 0_0123 2017-08-13 00:49:07
• Re:你们写代码都不写注释，这不是个好习惯，贴我的 (975) mhvvvv 2019-02-09 21:59:19