LZOI1397 题解

· · 个人记录

题意

给出 n 个物品的数量 m、体积 w、价值 s 以及背包的总体积 v。求背包里最大价值总和。

思路

使用类似01背包的思路，即：

{\large \sum_{i\le n}^{i=1} \sum_{j\ge w[i]}^{j=V} \sum_{k\le m[i]}^{k=1} dp[j]=max(dp[j],dp[j-k\times w[i]]+v[i]\times k) }

求出 dp[V] 即可。

#include<bits/stdc++.h>
using namespace std;
int n,V;
int m[100001],v[100001],w[100001];
int dp[100001];
int main(){
    cin>>n>>V;
    for(int i=1;i<=n;i++){
        cin>>m[i]>>w[i]>>v[i];
    }
    for(int i=1;i<=n;i++){
        for(int j=V;j>=w[i];j--){
            for(int k=1;k<=min(j/w[i],m[i]);k++){
                dp[j]=max(dp[j-w[i]*k]+v[i]*k,dp[j]);
            }
        }
    }
    cout<<dp[V]<<endl;
    return 0;
}