洛谷P3985 不开心的金明 题解

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

题意：

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

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

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

数据保证： max ⁡ ( v i ) − min ⁡ ( v i ) ≤ 3 max(v_i)-min(v_i) le 3 max(vi​)−min(vi​)≤3

数据范围： 1 ≤ N ≤ 100 , 1 ≤ p i ≤ 1 0 7 , 1 ≤ W , v i ≤ 1 0 9 1 le N le 100 ,1le p_i le 10^7,1 le W,v_i le 10^9 1≤N≤100,1≤pi​≤107,1≤W,vi​≤109

容易发现是01背包

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

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

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

于是我们找到 ∑ v i ′ sum v_i^prime ∑vi′​ ，从它开始枚举，并增加一维 k k k 表示装了 k k k 个物品

这样我们只要判断 j + k × min ⁡ ( v i ) ≤ W j+ktimesmin(v_i) le W j+k×min(vi​)≤W 就知道我们枚举的背包容量是否合法了

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

#include 
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;
}

转载请说明出处