P1064 金明的预算方案


背包其实就是把一个大问题拆分成若干个子问题，把一个要拿东西的动作按照题目要求分成若干个动作，分别枚举（DP其实就是非常的暴力），比较取最大值。
比如这道题，背包的物品之间是有依赖的，所以分情况讨论，考虑

  • 只放主件
  • 放主件和附件一（如果有的话）
  • 放主件和附件二
  • 放主件和两个附件

然后物品都只有一个，所以就是最普通的01背包。
其中 f [ i ] f[i] f[i]表示的是在背包的体积为 i i i 的时候的最优解。
最后跟普通的01背包一样输出 f [ v ] f[v] f[v]
关键是处理好分组 就没什么难度了。

#include<iostream>
#include<stdio.h>
#include<algorithm>
#define ls (p<<1)
#define rs (p<<1|1)
#define mid (l+r)/2
using namespace std;
typedef long long ll;
const ll N=1e6+7;
const double mod=2147483647.0;
const double EPS=1e-6;
struct node
{
    ll w,v;
}sur[N],sub[N][3];//sur主件sub附件sub[主件编号][附件编号]
ll n,m,a,b,c,f[N];
int main()
{
    scanf("%lld%lld",&n,&m);
    for(int i=1;i<=m;++i)
    {
        scanf("%lld%lld%lld",&a,&b,&c);
        if(!c)sur[i].w=a,sur[i].v=a*b;
        else {
            sub[c][0].w++;//点睛之笔
            sub[c][sub[c][0].w].w=a;
            sub[c][sub[c][0].w].v=a*b;
        }
    }
    for(int i=1;i<=m;++i)
    {
        for(int j=n;j>=sur[i].w&&sur[i].w;--j)//判断是否为主件
        {
            f[j]=max(f[j],f[j-sur[i].w]+sur[i].v);
            if(j>=sur[i].w+sub[i][1].w)//拿的下就拿来试试，下同
                f[j]=max(f[j],f[j-sur[i].w-sub[i][1].w]+sur[i].v+sub[i][1].v);
            if(j>=sur[i].w+sub[i][2].w)
                f[j]=max(f[j],f[j-sur[i].w-sub[i][2].w]+sur[i].v+sub[i][2].v);
            if(j>=sur[i].w+sub[i][1].w+sub[i][2].w)
                f[j]=max(f[j],f[j-sur[i].w-sub[i][1].w-sub[i][2].w]+sur[i].v+sub[i][1].v+sub[i][2].v);
        }
    }
    printf("%lld\n",f[n]);
    return 0;
}

有任何疑问欢迎评论哦虽然我真的很菜