背包问题

1. 01背包问题
2. 完全背包问题
3. 多重背包问题
4. 混合背包问题
5. 二维费用的背包问题
6. 分组背包问题
7. 背包问题求方案数
8. 求背包问题的方案
9. 有依赖的背包问题

1. 01 背包

二维

#include <cstdio>
#include <iostream>

using namespace std;

const int N = 1010;

int n, m;
int v[N], w[N];
int f[N][N];

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i ++ ) scanf("%d%d", &v[i], &w[i]);

    for (int i = 1; i <= n; i ++ )
        for (int j = 0; j <= m; j ++ )
        {
            f[i][j] = f[i - 1][j];  // 不选第 i 个
            if (v[i] <= j)  // 选第 i 个， 前提是有空间
                f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + w[i]);
        } 

    printf("%d\n", f[n][m]);

    return 0;
}

一维优化

#include <cstdio>
#include <iostream>

using namespace std;

const int N = 1010;

int n, m;
int v[N], w[N];
int f[N];

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i ++ ) scanf("%d%d", &v[i], &w[i]);

    for (int i = 1; i <= n; i ++ )
        for (int j = m; j >= v[i]; j -- )  // 选第 i 个时，f[j - v[i]] 要用前边的数据进行更新 所以倒序进行
            f[j] = max(f[j], f[j - v[i]] + w[i]);

    printf("%d\n", f[m]);

    return 0;
}

2. 完全背包

/*
for (int i = 1; i <= n; i ++ )
    for (int j = v[i]; j <= m; j ++ )
        f[j] = max(f[j], f[j - v[i]] + w[i]);

对于某个 j 而言， 如果最优解中包含 k 个v[i];

f[j - k * v[i]];

f[j - (k - 1) * v[i] - v[i]] + w[i]; 包含 1 个v[i]

...

f[j] f[j - v[i]] + w[i]
*/

f[i][j]

/*
f[i][j] 表示前i个物品最大体积不超过j的最大值
*/

朴素版

for (int i = 1; i <= n; i ++ )
    for (int j = 0; j <= m; j ++ )
        for (int k = 0; k <= j / v[i]; k ++ )  // 当 k == 0 时，就是没有选 k 时，f[i - 1][j]
            f[i][j] = max(f[i][j], f[i - 1][j - k * v[i]] + k * w[i]);

错位思想找规律

/*
f[i , j ] = max( f[i-1,j] , f[i-1,j-v]+w ,  f[i-1,j-2*v]+2*w , f[i-1,j-3*v]+3*w , .....)
f[i , j-v]= max(            f[i-1,j-v]   ,  f[i-1,j-2*v] + w , f[i-1,j-3*v]+2*w , .....)
由上两式，可得出如下递推关系： 
                        f[i][j] = max(f[i, j - v] + w , f[i - 1][j]) 
*/

for (int i = 1; i <= n; i++ )
    for (int j = 0; j <= m; j ++)
    {
        f[i][j] = f[i - 1][j];
        if (v[i] <= j)
            f[i][j] = max(f[i][j], f[i][j - v[i]] + w[i]);
    }

根据01背包优化思路 优化

for (int i = 1; i <= n; i ++ )
    for (int j = v[i]; j <= m; j ++ )
        f[j] = max(f[j], f[j - v[i]] + w[i]);

最终代码

#include <cstdio>
#include <iostream>

using namespace std;

const int N = 1010;

int n, m;
int v[N], w[N];
int f[N];

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i ++ ) scanf("%d%d", &v[i], &w[i]);

    for (int i = 1; i <= n; i ++ )
        for (int j = v[i]; j <= m; j ++ )
            f[j] = max(f[j], f[j - v[i]] + w[i]);

    printf("%d\n", f[m]);

    return 0;
}

3. 多重背包

#include <cstdio>
#include <iostream>

using namespace std;

const int N = 110;

int n, m;
int f[N];

int main()
{
    scanf("%d%d", &n, &m);

    for (int i = 1; i <= n; i ++ )
    {
        int v, w, s;
        scanf("%d%d%d", &v, &w, &s);
        for (int j = m; j >= 0; j -- )
            for (int k = 1; k <= s && k * v <= j; k ++ )
                f[j] = max(f[j], f[j - k * v] + k * w);
    }

    printf("%d\n", f[m]);

    return 0;
}

二进制优化

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

const int N = 2010;

int n, m;
int f[N];

struct Good
{
    int v, w;
};

int main()
{
    vector<Good> goods;
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i ++ )
    {
        int v, w, s;
        scanf("%d%d%d", &v, &w, &s);
        for (int k = 1; k <= s; k *= 2)  // 二进制优化
        {
            s -= k;
            goods.push_back({v * k, w * k});
        }
        if (s > 0) goods.push_back({v * s, w * s});
    }

    for (int i = 0; i < goods.size(); i ++ )
        for (int j = m; j >= goods[i].v; j -- )
            f[j] = max(f[j], f[j - goods[i].v] + goods[i].w);

    cout << f[m] << endl;

    return 0;
}

单调队列优化

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

using namespace std;

const int N = 20010;

int n, m;
int f[N], g[N], q[N];

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i ++ )
    {
        int v, w, s;
        scanf("%d%d%d", &v, &w, &s);
        memcpy(g, f, sizeof f);

        for (int j = 0; j < v; j ++ )
        {
            int hh = 0, tt = -1;
            for (int k = j; k <= m; k += v)
            {
                f[k] = g[k];
                if (hh <= tt && k - s * v > q[hh]) hh ++ ;
                if (hh <= tt) f[k] = max(f[k], g[q[hh]] + (k - q[hh]) / v * w);
                while (hh <= tt && g[q[tt]] - (q[tt] - j) / v * w <= g[k] - (k - j) / v * w) tt -- ;
                q[ ++ tt] = k;
            }
        }
    }

    printf("%d\n", f[m]);

    return 0;
}

4. 混合背包

分别记录各种背包的情况，多重背包用二进制优化成01背包

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

using namespace std;

const int N = 1010;

int n, m;
int f[N];

struct Thing{
    int kind;
    int v, w;
};

vector<Thing> things;

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i ++ )
    {
        int v, w, s;
        scanf("%d%d%d", &v, &w, &s);
        if (s < 0)  // 01背包
            things.push_back({-1, v, w});
        else if (s == 0)  // 完全背包
            things.push_back({0, v, w});
        else  // 多重背包
        {
            for (int k = 1; k <= s; k *= 2)  // 二进制优化 变 01背包
            {
                s -= k;
                things.push_back({-1, v * k, w * k});
            }
            if (s > 0) 
                things.push_back({-1, v * s, w * s});
        }
    }

    for (int i = 0; i < things.size(); i ++ )
    {
        Thing thing = things[i];
        if (thing.kind < 0)
            for (int j = m; j >= thing.v; j -- )
                f[j] = max(f[j], f[j - thing.v] + thing.w);
        else
            for (int j = thing.v; j <= m; j ++ )
                f[j] = max(f[j], f[j - thing.v] + thing.w);
    }

    printf("%d\n", f[m]);

    return 0;
}

5. 二维费用的背包问题

每个物品可以用一次 也是01背包问题 多加一层循环 从大到小开始

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

using namespace std;

const int N = 110;

int n, v, m;
int f[N][N];

int main()
{
    scanf("%d%d%d", &n, &v, &m);
    for (int i = 0; i < n; i ++ )
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        for (int j = v; j >= a; j -- )
            for (int k = m; k >= b; k -- )
                f[j][k] = max(f[j][k], f[j - a][k - b] + c);
    }

    printf("%d\n", f[v][m]);

    return 0;
}

6. 分组背包问题

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

using namespace std;

const int N = 110;

int n, m;
int f[N], v[N], w[N];

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i ++ )
    {
        int s;
        scanf("%d", &s);
        for (int j = 0; j < s; j ++ ) scanf("%d%d", &v[j], &w[j]);
        for (int j = m; j >= 0; j -- )
            for (int k = 0; k < s; k ++ )  // 循环每一种选法
                if (j >= v[k])
                    f[j] = max(f[j], f[j - v[k]] + w[k]);
    }

    printf("%d\n", f[m]);

    return 0;
}

7.背包问题求方案数

路径跟踪 g[i][j]
状态表示 g(i,j)———集合： 考虑前 i 个物品，当前已使用体积恰好是 j 的，且 价值 为最大的方案

状态表示 g(i,j)———属性： 方案的数量 Sum

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

using namespace std;

const int N = 1010, MOD = 1e9 + 7, INF = 1e9;

int n, m;
int f[N], g[N];  // g[i][j] 表示前i个物品体积不超过j的且取到最大价值的方案总数

int main()
{
    scanf("%d%d", &n, &m);
    g[0] = 1;
    for (int i = 1; i <= n; i ++ ) f[i] = -INF;
    for (int i = 0; i < n; i ++ )
    {
        int v, w;
        scanf("%d%d", &v, &w);
        for (int j = m; j >= v; j -- )
        {
            int t = max(f[j], f[j - v] + w);
            int s = 0;  // 记录满足的数量
            if (t == f[j]) s += g[j];
            if (t == f[j - v] + w) s += g[j - v];
            if (s >= MOD) s %= MOD;
            f[j] = t;
            g[j] = s;
        }
    }

    int maxw = 0;
    for (int i = 0; i <= m; i ++ ) maxw = max(maxw, f[i]);  // 找到最大价值，不一定用所有的体积
    int res = 0;
    for (int i = 0; i <= m; i ++ )
        if (maxw == f[i])
        {
            res += g[i];
            if (res >= MOD) res %= MOD;
        }

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

    return 0;
}

8.求背包问题的方案

字典序最小 从1号开始查找
for (int i = 1; i <= n; i ++ )
    if (f[i][m] = f[i + 1][m - v[i]] + w[i])  // 说明i + 1的最优解是选i转移过去的
        cout << i << ' '

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

using namespace std;

const int N = 1010;

int n, m;
int v[N], w[N];
int f[N][N];

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i ++ ) scanf("%d%d", &v[i], &w[i]);

    for (int i = n; i >= 1; i -- )  // 字典序输出最小的 查找时从1开始倒推 dp时从n开始
        for (int j = 0; j <= m; j ++ )
        {
            f[i][j] = f[i + 1][j];
            if (j >= v[i]) 
                f[i][j] = max(f[i][j], f[i + 1][j - v[i]] + w[i]);
        }

    for (int i = 1, j = m; i <= n; i ++ )
        if (j >= v[i] && f[i][j] == f[i + 1][j - v[i]] + w[i])
        {
            printf("%d ", i);
            j -= v[i];
        }

    return 0;
}

9.有依赖的背包问题

想要选择子节点就要连同父节点一起选择
可以把每一个节点看成分组背包中的一个组

从叶子节点开始往根节点做
f[i][j] 表示以i为根节点 且选择了i 体积不超过j 的最大值

​

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

using namespace std;

const int N = 110;

int n, m, root;
int h[N], e[N], ne[N], idx;
int v[N], w[N];
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(son);  // 递归到叶子节点
        for (int j = m - v[u]; j >= 0; j -- )  // 从大到小 因为已经选择u 最大体积为 m - v[u]
            for (int k = 0; k <= j; k ++ )  // 枚举该子节点在体积j下能使用的所有可能
                f[u][j] = max(f[u][j], f[u][j - k] + f[son][k]);
    }

    for (int j = m; j >= v[u]; j -- ) f[u][j] = f[u][j - v[u]] + w[u];  // 把u节点加入
    for (int j = 0; j < v[u]; j ++ ) f[u][j] = 0;  // 选不了u节点的置为0
}

int main()
{
    memset(h, -1, sizeof h);
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i ++ )
    {
        int p;
        scanf("%d%d%d", &v[i], &w[i], &p);
        if (p == -1) root = i;
        else add(p, i);
    }

    dfs(root);
    printf("%d\n", f[root][m]);

    return 0;
}