睿抗
7-2 拼题A打卡奖励
- 01背包问题
- 复杂度为O(N * M)= 5e8, 肯定超时,要换个思路。
- 我们看到金币的数量小于等于30,及价值的最大值为1000 * 10,我们可以考虑求价值为j时的最小体积。区别于第一种:体积为j时的最大价值。复杂度:1000 * 1000 * 30 = 3e7
- 空间为64B,所以我们考虑用一维数组优化。
#include<bits/stdc++.h>
#define int long long
#define endl "\n" //加快cout输出换行速度的
using namespace std;
const int N = 1e3 + 10, M = 3e4 + 10;
typedef pair<int, int> PII;
int f[M];
int v[N], w[N];
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
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];//价值
// 价值为j时的最小体积为多少
memset(f, 0x3f, sizeof f);
f[0] = 0;
for(int i = 1; i <= n ; i ++)
{
for(int j = M; j >= w[i]; j --)
{
f[j] = min(f[j], f[j - w[i]] + v[i]);
}
}
int res;
for(int j = 30000; j >= 0; j --)
{
if(f[j] <= m)
{
res = j;
break;
}
}
cout << res << endl;
return 0;
}