L3-2 拼题A打卡奖励 (30 分)

题目描述：

n张卡片，每张卡片有一个花费cost，一个价值val，你现在有m块钱，问最多能获得多大的价值

n <= 1000, m <= 365×24×60, cost <= 600, val <= 30

思路：

观察一下数据范围，发现普通的01背包复杂度是n*m,大概是5e8,会超时，我们得想办法优化一下

可以发现，每个卡片的价值其实不高，所以我们可以考虑交换价值和体积，将dp的第二维改成所有卡片的价值，这样的复杂度是1000 * (1000 * 30),也就是3e7，可以接受

所以dp[i][j]表示前i个物品，获得j的价值所需要最小的花费

滚掉第一维后，初始化dp[0] = 0,dp[i] = inf

dp[i] = min(dp[i], dp[i - val[i]] + cost[i]);

我们只需要从后往前枚举，看那个数的dp[i]<=m即可

#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
#define inf 0x3f3f3f3f
#define mod7 1000000007
#define mod9 998244353
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define debug(a) cout << "Debuging...|" << #a << ": " << a << "\n";
typedef long long ll;
typedef pair <int,int> pii;

#define MAX 300000 + 50
int n, m, k, x;
int cost[MAX];
int val[MAX];
int dp[MAX];
void work(){
    cin >> n >> m;
    for(int i = 1; i <= n; ++i)cin >> cost[i];
    for(int i = 1; i <= n; ++i)cin >> val[i];
    mem(dp, inf);
    dp[0] = 0;
    for(int i = 1; i <= n; ++i){
        for(int j = 30 * 1000; j >= val[i]; --j){
            dp[j] = min(dp[j], dp[j - val[i]] + cost[i]);
        }
    }
    for(int i = 30 * 1000; i >= 0; --i){
        if(dp[i] <= m){
            cout << i << endl;
            return;
        }
    }
}


int main(){
    io;
    work();
    return 0;
}