E - Knapsack 2

题目链接

大致题意:

略~

解题思路:

01背包

背包重量1e9,传统方法必然超时

但是N*v最大是1e5,所以我们可以枚举价值

状态表示:f[i]表示i价值所需要的最小体积

只要f[i]<=m,就更新res

AC代码:

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 1; i <= (n); ++i)
#define debug(c) cout << #c << " = " << c << endl;
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const int N = 1e5 + 10;
int n, m;
ll f[N]; //表示i价值所需要的最小体积
int main(void)
{
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
	ios::sync_with_stdio(0); cin.tie(0);
	cin >> n >> m;
	memset(f, INF, sizeof f);
	f[0] = 0;
	int res = 0;
	for (int i = 1; i <= n; ++i) {
		int w, v; cin >> w >> v;
		for (int j = 1e5; j >= v; --j) {  //价值
			f[j] = min(f[j], f[j - v] + w);
			if (f[j] <= m)res = max(res, j);
		}
	}
	cout << res << endl;
	return 0;
}