题目：
1.实则为一个01背包问题。
2.使用动态规划求解：
dp[i][j]表示从前i个物品开始选择，重量不超过j时，背包的最大价值。
dp[n][m]为最终答案。
状态转移方程为：
//背包空余重量不足
if (weight[i]>j) dp[i + 1][j] = dp[i][j];
//动态规划，选和不选的情况
else
dp[i + 1][j] = max(dp[i][j], dp[i][j – weight[i]] + value[i]);
3.写了两个版本，其中一个是没有优化的，一个是优化的版本。其中需要注意：
（1）优化版本只采用dp[j]
（2）因为dp[i + 1][j] = max(dp[i][j], dp[i][j – weight[i]] + value[i])需要使用到dp[i][j-weight[i]]的值，所以在遍历重量的时候需要从后面开始遍历：
for (int j = m; j >= 0; j–)
描述
且说上一周的故事里，小Hi和小Ho费劲心思终于拿到了茫茫多的奖券！而现在，终于到了小Ho领取奖励的时刻了！
小Ho现在手上有M张奖券，而奖品区有N件奖品，分别标号为1到N，其中第i件奖品需要need(i)张奖券进行兑换，同时也只能兑换一次，为了使得辛苦得到的奖券不白白浪费，小Ho给每件奖品都评了分，其中第i件奖品的评分值为value(i),表示他对这件奖品的喜好值。现在他想知道，凭借他手上的这些奖券，可以换到哪些奖品，使得这些奖品的喜好值之和能够最大。
输入
每个测试点（输入文件）有且仅有一组测试数据。
每组测试数据的第一行为两个正整数N和M,表示奖品的个数，以及小Ho手中的奖券数。
接下来的n行描述每一行描述一个奖品，其中第i行为两个整数need(i)和value(i)，意义如前文所述。
测试数据保证
对于100%的数据，N的值不超过500，M的值不超过10^5
对于100%的数据，need(i)不超过2*10^5, value(i)不超过10^3
输出
对于每组测试数据，输出一个整数Ans，表示小Ho可以获得的总喜好值。
- 样例输入
-
5 1000 144 990 487 436 210 673 567 58 1056 897
- 样例输出
-
2099
AC代码：
/*
题目：
1.实则为一个01背包问题。
2.使用动态规划求解：
dp[i][j]表示从前i个物品开始选择，重量不超过j时，背包的最大价值。
dp[n][m]为最终答案。
状态转移方程为：
//背包空余重量不足
if (weight[i]>j) dp[i + 1][j] = dp[i][j];
//动态规划，选和不选的情况
else
dp[i + 1][j] = max(dp[i][j], dp[i][j - weight[i]] + value[i]);
3.写了两个版本，其中一个是没有优化的，一个是优化的版本。其中需要注意：
（1）优化版本只采用dp[j]
（2）因为dp[i + 1][j] = max(dp[i][j], dp[i][j - weight[i]] + value[i])需要使用到dp[i][j-weight[i]]的值，所以在遍历重量的时候需要从后面开始遍历：
for (int j = m; j >= 0; j--)
*/
/*
*/
#include<string>
#include <iomanip>
#include<fstream>
#include<set>
#include<queue>
#include<map>
//#include<unordered_set>
//#include<unordered_map>
//#include <sstream>
//#include "func.h"
//#include <list>
#include<stdio.h>
#include<iostream>
#include<string>
#include<memory.h>
#include<limits.h>
//#include<stack>
#include<vector>
#include <algorithm>
using namespace std;
/*
函数名 ：main
函数功能：主函数
*/
int main(void)
{
/*
int n, m;
cin >> n >> m;
vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));
vector<int> value(n, 0);
vector<int> weight(n, 0);
for (int i = 0; i < n; i++)
{
scanf("%d %d", &weight[i], &value[i]);
}
for (int i = 0; i < n; i++)
{
for (int j = 0; j <= m; j++)
{
//背包空余重量不足
if (weight[i]>j) dp[i + 1][j] = dp[i][j];
//动态规划，选和不选的情况
else
dp[i + 1][j] = max(dp[i][j], dp[i][j - weight[i]] + value[i]);
}
}
cout << dp[n][m] << endl;
*/
//优化版本:
int n, m;
cin >> n >> m;
vector<int> dp(m + 1, 0);
vector<int> value(n, 0);
vector<int> weight(n, 0);
for (int i = 0; i < n; i++)
{
scanf("%d %d", &weight[i], &value[i]);
}
for (int i = 0; i < n; i++)
{
for (int j = m; j >= 0; j--)
{//因为dp[j-weight[i]]是引用了前面的数组，所以需要从后面开始遍历
//背包空余重量不足
if (weight[i]>j) dp[j] = dp[j];
//动态规划，选和不选的情况
else
dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
}
}
cout << dp[m] << endl;
return 0;
}