有依赖的背包---P1064 金明的预算方案

P1064 金明的预算方案

solution 1 暴搜 70pt

dfs （当前搜到了第几个物品，产生的总价值，剩下多少钱）

剪枝 1：如果剩下的钱数<0，直接return就好，没必要继续了

剪枝 2：如果所有物品都搜完了，结果记录一下

然后vis数组记录这个物品的主件有没有买，分两种情况继续往下搜，买该物品（前提合法）或者不买

注意没有主件的物品我们就标记它的主件是编号为0，我们买了它

code 

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<algorithm>

#include<cmath>

#include<cstring>

#include<string>

#include<queue>

using namespace std;

typedef long long ll;

inline int read(){

    int ans=;

    char last=' ',ch=getchar();

    while(ch<''||ch>'') last=ch,ch=getchar();

    while(ch>=''&&ch<='') ans=ans*+ch-'',ch=getchar();

    if(last=='-') ans=-ans;

    return ans;

}

int n,m;

int v[],w[],q[];

bool vis[];

int ans=;

void dfs(int pos,int sum,int res)

{

    if(res<) return ;

    if(pos>m) {

        ans=max(ans,sum);

        return ;

    }

    if(res>=v[pos]&&vis[q[pos]]==) vis[pos]=,dfs(pos+,sum+w[pos],res-v[pos]);

    vis[pos]=;

    dfs(pos+,sum,res);

}

int main()

{

    n=read();m=read();

    for(int i=;i<=m;i++){

        v[i]=read();

        w[i]=read();w[i]=w[i]*v[i];

        q[i]=read();

    }

    vis[]=;

    dfs(,,n);

    printf("%d\n",ans);

    return ;

}

solution 2 有依赖的背包 100pt

这道题目比较简单，可以转化成分组背包做

我们观察每个主件只有0~2个附件

（1）对于有主件的物品来说，它可以和主件划分为一类物品，那么对于这一类物品，我们有4种决策，一个也不买，只买主件，买主件和附件1，买主件和附件2，买主件和附件1和附件2，但是这4种决策是互斥的，所以可以转化成分组背包做【ps：可能一个主件只有一个附件】

（2）对于没有主件的物品来说，它本身自成一类，和上面的分组同理

code

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<algorithm>

#include<cmath>

#include<cstring>

#include<string>

#include<queue>

using namespace std;

typedef long long ll;

inline int read(){

    int ans=;

    char last=' ',ch=getchar();

    while(ch<''||ch>'') last=ch,ch=getchar();

    while(ch>=''&&ch<='') ans=ans*+ch-'',ch=getchar();

    if(last=='-') ans=-ans;

    return ans;

}

int n,m;

int v[],w[],q[];

bool vis[];

int ans=;

void dfs(int pos,int sum,int res)

{

    if(res<) return ;

    if(pos>m) {

        ans=max(ans,sum);

        return ;

    }

    if(res>=v[pos]&&vis[q[pos]]==) vis[pos]=,dfs(pos+,sum+w[pos],res-v[pos]);

    vis[pos]=;

    dfs(pos+,sum,res);

}

int main()

{

    n=read();m=read();

    for(int i=;i<=m;i++){

        v[i]=read();

        w[i]=read();w[i]=w[i]*v[i];

        q[i]=read();

    }

    vis[]=;

    dfs(,,n);

    printf("%d\n",ans);

    return ;

}