题目连接：点击打开链接
解题思路：
典型的01背包，，非常省空间的一种写法。
完整代码：
#include <iostream>#include <cstdio>#include <cstring>#include <climits>using namespace std;const int maxn = 111001;int n , m;int need[maxn] , val[maxn] , dp[maxn];int main(){#ifdef DoubleQfreopen("in.txt" , "r" , stdin);#endifwhile(cin >> n >> m){memset(dp , 0 , sizeof(dp));for(int i = 1 ; i <= n ; i ++)cin >> need[i] >> val[i];for(int i = 1 ; i <= n ; i ++){for(int j = m ; j >= need[i] ; j –){dp[j] = max(dp[j] , dp[j-need[i]] + val[i]);}}cout << dp[m] << endl;}}
也有伤心的，既有令人兴奋的，也有令人灰心的，
