题目 

解法

如果直接上一维空间优化，也会因为时间上限太大而超时

注意到价值上限较小，于是将VW转换

状态定义从f(i, j) 1-i物品逐个决策，使得时间不超过j，价值最大 改为：

1-i物品逐个决策，使得价值正好等于j，用时最小

目标状态从f(n,m)变为代码尾所示

（为啥不超过变为正好，要结合转移的路径来分析哈，碰巧确实是这样）

代码

#include <bits/stdc++.h>
using namespace std;const int N = 1010;
const int M = 30 * N;int f[M];
int w[N], v[N];int main()
{int n, m;cin >> n >> m;for(int i = 1; i <= n; i++)cin >> v[i];for(int i = 1; i <= n; i++)cin >> w[i];memset(f, 0x3f, sizeof f);f[0] = 0;for(int i = 1; i <= n; i++)for(int j = n * 30; j >= w[i]; j--)f[j] = min(f[j], f[j-w[i]] + v[i]);for(int i = n*30; i >= 0; i--){if(f[i] > m) continue;cout << i;break;}
}