题解 P1782 【旅行商的背包】

· · 题解

纪念一下学会多重背包，发一个题解

这题就是一个裸的多重背包，无非多了一个关于奇货的操作，也还是很简单的

关于多重背包，有两种优化，一种是二进制优化，另一种是单调队列

但是单调队列并不在NOIP考察范围之内，这里就不做介绍，有兴趣的可以做一下这个板子

下面说一下二进制优化多重背包

首先讲一下多重背包最容易想到的暴力法

由于多重背包问题是介于01背包和完全背包之间的一种问题，我们很容易想到枚举选取的物品个数

假如对于一种数量为n[i]的物品，令f[i][v]表示前i种物品恰放 入一个容量为v的背包的最大权值，则有状态转移方程：

 f[i][v] = max(f[i-1][v-k*c[i]]+ k * w[i])

但是很显然，复杂度是O(V * Σn[i])，对于大数据来说是绝对炸飞的

那么我们尝试将其转化为01背包进行求解

把第i种物品换成n[i]件01背包中的物品，则得到了物品数为Σn[i]的01背包问题，直接求解，复杂度仍然是O(V * Σn[i])

小数据可以这样搞一下，大数据仍然炸飞

接下来我们考虑二进制优化思想

将第i种物品分成若干件物品，其中每件物品有一个系数，这件物品的费用和价值均是原来的费用和价值乘以这个系数

使这些系数分别为1,2,4,...,2^(k-1),n[i]-2^k+1，且k是满足n[i]-2^k+1>0的最大整数。例如，如果n[i]为13，就将这种物品分成系数分别为1,2,4,6的四件物品

分成的这几件物品的系数和为n[i]，表明不可能取多于n[i]件的第i种物品。另外这种方法也能保证对于0..n[i]间的每一个整数，均可以用若干个系数的和表示，这个证明可以分0..2^k-1和2^k..n[i]两段来分别讨论得出，并不难

这样一来，复杂度就改进了许多，变成了O(V * Σlog n[i])

当然多重背包还有一种更为快速的优化，就是我前面提到的单调队列优化

这个算法的思路是基于基本算法的状态转移方程，但应用单调队列的方法使每个状态的值可以以均摊O(1)的时间求解，总的复杂度是O(V * n)，有能力的神仙可以尝试一下，本蒟蒻在这里就不作详细说明

下面是二进制优化的代码

#include <iostream>
#include <cmath>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
using namespace std;
inline int read(){
    int res=0,f=1;char ch=' ';
    while(!isdigit(ch)){if(ch=='-') f=-1;ch=getchar();}
    while(isdigit(ch)){res=res*10+ch-'0';ch=getchar();}
    return res*f;
}
void write(int x){
    if(x<0){putchar('-');x=-x;}
    if(x>9) write(x/10);
    putchar(x%10+'0');
}
int max(int a,int b){
    return a>b?a:b;
}
const int N=1e5+5;
int n,m,T,dp[N],a,b,c,v,w,d;
void zeroone(int cost,int weight,int V){
    for(register int i=V;i>=cost;i--)
        dp[i]=max(dp[i],dp[i-cost]+weight);
}
void complete(int cost,int weight,int V){
    for(register int i=cost;i<=V;i++)
        dp[i]=max(dp[i],dp[i-cost]+weight);
}
void mutil(int cost,int weight,int num,int V){//二进制优化的多重背包
    if(cost*num>=V){//如果无法将所有物品装下，直接跑一个完全背包
        complete(cost,weight,V);
        return;
    }
    for(register int i=1;i<=num;i*=2){//二进制优化
        zeroone(i*cost,i*weight,V);
        num-=i;
    }
    if(num)zeroone(num*cost,num*weight,V);//如果有多余的，单独跑一个01背包
}
int main()
{
    n=read(),m=read(),T=read();
    for(register int i=1;i<=n;i++)
        v=read(),w=read(),d=read(),mutil(v,w,d,T);
    for(register int i=1;i<=m;i++){
        a=read(),b=read(),c=read();
        for(register int j=T;j>=0;j--)
            for(register int u=0;u<=j;u++)dp[j]=max(dp[j],dp[j-u]+a*u*u+b*u+c);
    }
    write(dp[T]);
    return 0;
}