官方题解

T3 午枫爱搬家2

题目大意

有 $n$ 件物品，每件物品有体积和价值两种属性，有一辆容量为 $m$ 的卡车，求搬运的物品在没超过卡车容量的前提下最大能存放的价值。

解题思路

本题考虑用 $01$ 背包求解。

设 $dp_{j}$ 表示消耗 $j$ 的容积时，能得到的最大价值。

那么状态转移为 $dp_{j}=max(dp_{j},dp_{j-w_i}+v_i)$ 。

参考代码

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'

signed main(){
    int n,m;cin>>n>>m;
    vector<int>w(n+1),v(n+1);
    for(int i=1;i<=n;i++) cin>>w[i]>>v[i];

    vector<int>dp(m+1);
    for(int i=1;i<=n;i++){
        for(int j=m;j>=w[i];j--){
            dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
        }
    }

    cout<<dp[m]<<endl;
}