题解：P1782 旅行商的背包

Taper_XZD · 2025-11-19 23:29:19 · 题解

题意

• 普通物品第 i 种可选 D_i 件；
  奇货第 i 件满足体积 X_i 到价值 Y_i 的函数：

• 求最大收益。

  思路

  首先考虑普通物品

  多重背包易得，考虑二进制优化。

  基于倍增思想，举个例子，当我们想拿 1024 个物品时，我们会去枚举 1 到 1024，但是若我们 1,2,4,8\ldots 512,1024 这样去拿，最终结果仍然与朴素做法一样，但是仅仅 10 次就可以得出答案，所以我们是把 C_i 拆成 2^0+2^1+2^2+\ldots+2^{\log_2{C_i−1}}+x 的形式。

引自：【学习笔记】多重背包优化

学会二进制优化后，想必你能够敲出这段板子：

int ww,vv,d;  //体积,价值,数量
cin>>ww>>vv>>d;
//二进制优化
int k=1;
while(k<=d){
    cnt++;
    w[cnt]=k*ww;
    v[cnt]=k*vv;
    d-=k;
    k*=2;
}
if(d>0){
     cnt++;
     w[cnt]=d*ww;
     v[cnt]=d*vv;
}

多重背包被我们转化为01背包。

• 1$ 到 $cnt$ 枚举每个物品 $i
• C$ 到 $W_i$ 反向枚举每个容量 $j

愉快地写出状态转移方程：

然后看看奇货们

进行一个数据范围的查看。

这么点大，直接枚举 X_i 肯定没问题。
可以在原 dp 数组基础上处理每个奇货。

• C$ 到 $0$ 反向枚举每个容量 $j
• 0$ 到 $j$ 枚举体积 $X

愉快地写出第二个状态转移方程：

最后记得取一个最大值输出。

完整代码

#include<bits/stdc++.h>
#define int long long  //不开long long见祖宗
#define f(x,y,z) for(int x=y;x<=z;x++)  //正向循环
#define fw(x,y,z) for(int x=y;x>=z;x--)  //反向循环
using namespace std;

const int N=1e6+5;  //拆分后物品数量增多,故N取大一些
int n,m,c,cnt,ans;
int v[N],w[N],dp[N];

signed main(){
    cin>>n>>m>>c;
    //输入&优化处理
    f(i,1,n){
        int ww,vv,d;  //体积,价值,数量
        //个人更习惯用v(value)表示价值,用w(weigh)表示重量,与题目变量相反
        cin>>ww>>vv>>d;  
        //二进制优化
        int k=1;
        while(k<=d){
            cnt++;
            w[cnt]=k*ww;
            v[cnt]=k*vv;
            d-=k;
            k*=2;
        }
        if(d>0){
            cnt++;
            w[cnt]=d*ww;
            v[cnt]=d*vv;
        }
    }
    //处理普通物品
    f(i,1,cnt)
        fw(j,c,w[i])
            dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
    //奇货
    f(i,1,m){
        int a,b,c_;
        cin>>a>>b>>c_;
        //在原dp数组基础上处理每个奇货
        fw(j,c,0)
            f(x,0,j)  //从0至j枚举x
                dp[j]=max(dp[j],dp[j-x]+a*x*x+b*x+c_);
    }

    cout<<*max_element(dp,dp+c+1)<<endl;  //最大元素函数
    return 0;
}