有依赖的背包问题题目链接

10. 有依赖的背包问题 - AcWing题库

有依赖的背包问题题目类型

链表存图+dfs+分组背包问题

有依赖的背包问题模板代码

#include<cstring>
#include<iostream>
#include<algorithm>

using namespace std;

const int N = 110;

int n, m;
int v[N], w[N];
int h[N], e[N], ne[N], idx;
int f[N][N];

void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

void dfs(int u)
{
    for(int i=h[u];~i;i=ne[i]) // 循环物品组
    {
        int son = e[i];
        dfs(e[i]);
        
        for(int j=m-v[u];j>=0;j--) // 循环体积
        {
            for(int k=0;k<=j;k++) // 循环决策
            {
                f[u][j]=max(f[u][j],f[u][j-k]+f[son][k]);
            }
        }
    }
    // 将物品u加进去
    for(int i=m;i>=v[u];i--) f[u][i] = f[u][i-v[u]]+w[u];
    for(int i=0;i<v[u];i++) f[u][i]=0;
}

int main(){
    cin >> n >> m;
    memset(h, -1, sizeof(h));
    int root;
    for(int i=1;i<=n;i++)
    {
        int p;
        cin>>v[i]>>w[i]>>p;
        if(p==-1) root = i;
        else add(p, i);
    }
    dfs(root);
    cout<<f[root][m]<<endl;
    return 0;
}

背包问题求方案数题目链接

11. 背包问题求方案数 - AcWing题库

背包问题求方案数题目类型

求方案数

背包问题求方案数模板代码

#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

const int N = 1010, mod = 1e9 + 7;
int n, m;
int f[N], g[N];
int main()
{
    cin>>n>>m;
    memset(f, -0x3f, sizeof(f));
    f[0] = 0;
    g[0] = 1;
    
    for(int i=0;i<n;++i)
    {
        int v, w;
        cin>>v>>w;
        for(int j=m;j>=v;j--)
        {
            int maxv = max(f[j], f[j-v]+w);
            int cnt = 0;
            if (maxv == f[j]) cnt += g[j];
            if (maxv == f[j-v]+w) cnt += g[j-v];
            g[j] = cnt % mod;
            f[j] = maxv;
        }
    }
    int res = 0;
       for(int i=0;i<=m;i++) res = max(res, f[i]);
    int cnt = 0;
    for(int i=0;i<=m;i++)
        if(res == f[i])
            cnt = (cnt + g[i]) % mod;
    cout << cnt << endl;
    return 0;
}

能量石题目链接

734. 能量石 - AcWing题库

能量石题目类型

贪心+dp

能量石代码

#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 10010;

int n;
struct Stone
{
    int s, e, l;
    bool operator< (const Stone &W) const
    {
        return s * W.l < l * W.s;
    }
}stone[N];
int f[N];
int main(){
    int T;
    cin>>T;
    for(int C=1;C<=T;C++)
    {
        int m = 0;
        cin>>n;
        for(int i=0;i<n;++i)
        {
            int s, e, l;
            cin>>s>>e>>l;
            stone[i] = {s, e, l};
            m+=s;
        }
        sort(stone, stone + n);
           memset(f, -0x3f, sizeof(f));
        f[0]=0;
        for(int i=0;i<n;++i)
        {
            int s = stone[i].s, e = stone[i].e, l = stone[i].l;
            for(int j=m;j>=s;j--)
                f[j] = max(f[j],f[j-s]+e-(j-s)*l);
        }
        int res = 0;
        for(int i=0;i<=m;i++) res = max(res, f[i]);
        printf("Case #%d: %d\n", C, res);
    }
    return 0;
}