睿抗

7-2 拼题A打卡奖励

• 思路

1. 01背包问题
2. 复杂度为O（N * M）= 5e8, 肯定超时，要换个思路。
3. 我们看到金币的数量小于等于30，及价值的最大值为1000 * 10，我们可以考虑求价值为j时的最小体积。区别于第一种：体积为j时的最大价值。复杂度：1000 * 1000 * 30 = 3e7
4. 空间为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;
}