题解 P1064 【金明的预算方案】

· · 题解

更新，加入便于阅读的版本，增加可读性

话说说这个代码不好理解的，你们怕是没见过rqy和zyb的代码压行比赛

好久没做背包的题了，有点生，回去刷几道水题找找感觉，又遇到了这道金明的预算方案

思路很简单，配件不单独拿出来，我们只处理主件，配件绑定主件处理。

那么对于每一个主件i和它的两个配件j，k，一共有五种情况，分别是：

1.一个也不选

2.只选择主件i

3.选择主件i和附件j

4.选择主件i和附件k

5.选择主件i以及附件j，k

那么状态转移方程也就出来了，我们用w数组表示价值，v数组表示体积,用m表示背包当前容积，也就是

f[m]=max(f[m],f[m-v[i]]+w[i],f[m-v[i]-v[j]]+w[i]+w[j],f[m-v[i]-v[k]]+w[i]+w[k],f[m-v[i]-v[j]-v[k]]+w[i]+w[j]+w[k])

要注意的是，本题有两个可以优化的点，一是每件物品的价格都是整十，那么如果m非整十，那么它非整十的部分也无法利用，那么我们就把每件物品的体积还有背包总容积都除以10，输出的时候再乘十即可。第二个点就是重要度在输入的时候直接乘到价值上即可

应大家的要求，先放一个把方程拆开了的版本，便于理解

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cctype>
#define ll long long
#define gc() getchar()
#define maxn 65
#define maxm 20005
using namespace std;

inline ll read(){    //日常读入优化，对这道题毫无卵用
    ll a=0;int f=0;char p=gc();
    while(!isdigit(p)){f|=p=='-';p=gc();}
    while(isdigit(p)){a=(a<<3)+(a<<1)+(p^48);p=gc();}
    return f?-a:a;
}
void write(ll a){
    if(a>9)write(a/10);
    putchar(a%10+'0');
}

int n,m,v[maxn],w[maxn],f[maxm],c[maxn][maxn];  //c[i][0]表示主件为i的物品的数量，那么c[0][0]就表示主件的数量，c[i][j]表示主件为i的第j个物品的标号，这样写本意是处理无穷个配件，结果发现配件至多有两个，懒得改了
int main(){
    m=read()/10;n=read();
    for(int i=1;i<=n;++i){
        v[i]=read()/10;w[i]=read()*v[i];
        int q=read();c[q][++c[q][0]]=i;
    }
    for(int i=1;i<=c[0][0];++i)
        for(int k=m;k>=v[i];--k){
            int v2=(k-v[c[0][i]])>=0?f[k-v[c[0][i]]]+w[c[0][i]]:0;    //可选则存为可存入的，不可选则为0，以下同此，v2,v3,v4,v5分别代表的是前面讲的第二第三第四第五种情况
            int v3=(k-v[c[0][i]]-v[c[c[0][i]][1]])>=0?f[k-v[c[0][i]]-v[c[c[0][i]][1]]]+w[c[0][i]]+w[c[c[0][i]][1]]:0;    
            int v4=(k-v[c[0][i]]-v[c[c[0][i]][2]])>=0?f[k-v[c[0][i]]-v[c[c[0][i]][2]]]+w[c[0][i]]+w[c[c[0][i]][2]]:0;
            int v5=(k-v[c[0][i]]-v[c[c[0][i]][1]]-v[c[c[0][i]][2]])>=0?f[k-v[c[0][i]]-v[c[c[0][i]][1]]-v[c[c[0][i]][2]]]+w[c[0][i]]+w[c[c[0][i]][1]]+w[c[c[0][i]][2]]:0;
            f[k]=max(f[k],max(max(v2,v3),max(v4,v5)));  //简化后应该就比较容易看懂了
        }
    write(f[m]*10);
    return 0;
}

原来的代码

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cctype>
#define ll long long
#define gc() getchar()
#define maxn 65
#define maxm 20005
using namespace std;

inline ll read(){    //日常读入优化，对这道题毫无卵用
    ll a=0;int f=0;char p=gc();
    while(!isdigit(p)){f|=p=='-';p=gc();}
    while(isdigit(p)){a=(a<<3)+(a<<1)+(p^48);p=gc();}
    return f?-a:a;
}
void write(ll a){
    if(a>9)write(a/10);
    putchar(a%10+'0');
}

int n,m,v[maxn],w[maxn],f[maxm],c[maxn][maxn];  //c[i][0]表示主件为i的物品的数量，那么c[0][0]就表示主件的数量，c[i][j]表示主件为i的第j个物品的标号，这样写本意是处理无穷个配件，结果发现配件至多有两个，懒得改了
int main(){
    m=read()/10;n=read();
    for(int i=1;i<=n;++i){
        v[i]=read()/10;w[i]=read()*v[i];
        int q=read();c[q][++c[q][0]]=i;
    }
    for(int i=1;i<=c[0][0];++i)
        for(int k=m;k>=v[i];--k)
            f[k]=max(f[k],max(max((k-v[c[0][i]])>=0?f[k-v[c[0][i]]]+w[c[0][i]]:0,(k-v[c[0][i]]-v[c[c[0][i]][1]])>=0?f[k-v[c[0][i]]-v[c[c[0][i]][1]]]+w[c[0][i]]+w[c[c[0][i]][1]]:0),max((k-v[c[0][i]]-v[c[c[0][i]][2]])>=0?f[k-v[c[0][i]]-v[c[c[0][i]][2]]]+w[c[0][i]]+w[c[c[0][i]][2]]:0,(k-v[c[0][i]]-v[c[c[0][i]][1]]-v[c[c[0][i]][2]])>=0?f[k-v[c[0][i]]-v[c[c[0][i]][1]]-v[c[c[0][i]][2]]]+w[c[0][i]]+w[c[c[0][i]][1]]+w[c[c[0][i]][2]]:0)));  //表面上这个地方很复杂，实际上原理很简单，就是上面我们所说的5种情况
    write(f[m]*10);
    return 0;
}