洛谷P3985 不开心的金明 题解

题目链接：P3985 不开心的金明

题意：

金明今天很不开心，家里购置的二手房就要领钥匙了，房里并没有一间他自己专用的很宽敞的房间。更让他不高兴的是，妈妈昨天对他说：“你需要购买哪些物品，怎么布置，你说了不算（有很大的限制），而且不超过 \(W\) 元钱。”。今天一早金明就开始做预算，但是他想买的东西太多了，肯定会超过妈妈限定的 \(W\) 元。于是，他把每件物品规定了一个重要度整数 \(p_i\) 表示。他还从因特网上查到了每件物品的价格 \(v_i\) （都是整数元）。

妈妈看到购物单后进行了审查，要求购物单上所有的物品价格的极差（最贵的减去最便宜的）不超过\(3\)（当然金明至今不知道为什么会这样）。他希望在不超过 \(W\) 元（可以等于 \(W\) 元）的前提下，使购买的重要度总和 \(\sum p_i\) 的最大。

请你帮助金明设计一个满足要求的购物单，你只需要告诉我们重要度的最大的和。

数据保证：\(\max(v_i)-\min(v_i) \le 3\)

数据范围：\(1 \le N \le 100 ,1\le p_i \le 10^7,1 \le W,v_i \le 10^9\)

容易发现是01背包

这个极差不超过 \(3\) 根本不用管，都保证了。

注意到这个费用很大但是极差很小，于是把所有的花费全部减去 \(\min(v_i)\)

但是这个 \(W\) 巨大，不可能按照 \(j=W \to 1\) 去枚举

于是我们找到 \(\sum v_i^\prime\) ，从它开始枚举，并增加一维 \(k\) 表示装了 \(k\) 个物品

这样我们只要判断 \(j+k\times\min(v_i) \le W\) 就知道我们枚举的背包容量是否合法了

代码：（变量名和上面的陈述完全不一样）

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define N (int)(105)

int n,m,sum;
int w[N],v[N],mn=INF,dp[N*5][N];
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n >> m;
    for(int i=1; i<=n; i++)
    {
        cin >> w[i] >> v[i];
        mn=min(mn,w[i]);sum+=w[i]; // 确实，但是，代码写的是w[i] qwq
    }
    for(int i=1; i<=n; i++) w[i]-=mn;
    sum-=n*mn;
    for(int i=1; i<=n; i++)
        for(int j=sum; j>=w[i]; j--)
            for(int k=n; k>=1; k--)
                if(j+k*mn<=m)
                {
                    dp[j][k]=max(dp[j][k],dp[j-w[i]][k-1]+v[i]);
                }
    int res=0;
    for(int i=1; i<=sum; i++)
        for(int j=1; j<=n; j++)
            res=max(res,dp[i][j]);
    cout << res;
    return 0;
}