题解 P3985 【不开心的金明】

蓝莲花__ · 2019-10-01 21:32:52 · 题解

这是一道大水题！？

在做完 开心的金明 和 金明的储蓄计划 后

发现这也是一个简单的背包

在预处理时将每个物品的体积都减去（MINV-1）

其中MINV是所以物品中的最小的体积（价值）

再在dp数组中多加一维，记录一共选了几个

这样做的目的是可以知道当前选的总体积

dp[i][j]表示我选的修改后的物品的体积为i，选了j个

则当前的总体积为：i+j*minv ! ! !

好好理解！！！

代码不长

#include<bits/stdc++.h>
using namespace std;
const int mx=110;
int dp[mx*5][mx],n,w[mx],v[mx],sumv,minv=1e10,sv;
int main()
{
    cin>>n>>sumv;
    for (int i=1;i<=n;i++) cin>>v[i]>>w[i],minv=min(minv,v[i]),sv+=v[i];
    minv--;
        for (int i=1;i<=n;i++) v[i]-=minv;
        sv-=n*minv;
    for (int i=1;i<=n;i++)
    for (int j=sv;j>=v[i];j--)
    for (int k=n;k>=1;k--)
    if (j+k*minv<=sumv) dp[j][k]=max(dp[j][k],dp[j-v[i]][k-1]+w[i]);//cout<<dp[j][k]<<" "<<j<<" "<<k<<endl;

    int ans=0;
    for (int j=1;j<=sv;j++)
    for (int i=1;i<=n;i++) ans=max(ans,dp[j][i]);
    cout<<ans;
    return 0;
}