题解：P1782 旅行商的背包

题意

$C$ 容量背包。
$n$ 种普通物品， $m$ 种奇货。
普通物品第 $i$ 种可选 $D_i$ 件；
奇货第 $i$ 件满足体积 $X_i$ 到价值 $Y_i$ 的函数：

Y_i=a_iX_i^2+b_iX_i+c_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$ 的形式。

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

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

CPP

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$

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

dp_j=\max(dp_j,dp_{j-w_i}+v_i)

然后看看奇货们

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

1\le m\le 5

这么点大，直接枚举

X_i

肯定没问题。
可以在原

dp

数组基础上处理每个奇货。

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

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

dp_j=\max(dp_j,dp_{j-X}+ax^2+bx+c)

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

完整代码

CPP

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

题解：P1782 旅行商的背包

文章操作

题意

思路

首先考虑普通物品

然后看看奇货们

完整代码

相关推荐

评论

题解：P1782 旅行商的背包