背包九讲

01 背包

题目描述

有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。

第 i 件物品的体积是 v_i，价值是 w_i。

求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。

输出最大价值。

输入格式

第一行两个整数，$N, V$，用空格隔开，分别表示物品数量和背包容积。

接下来有 N 行，每行两个整数 v_i, w_i，用空格隔开，分别表示第 i 件物品的体积和价值。

输出格式

输出一个整数，表示最大价值。

数据范围

0 < N , V ≤ 1000

0 < v_i, w_i ≤ 1000

输入样例

4 5
1 2
2 4
3 4
4 5

输出样例：

8

CODE

二维常规版

#include <bits/stdc++.h>
using namespace std;

const int N = 1e3 + 10;
int dp[N][N] = {0};

int main()
{
    int n, v;
    cin >> n >> v;
    vector<pair<int, int>> a(n + 1);
    for (int i = 1; i <= n; i ++)
        cin >> a[i].first >> a[i].second;
    for (int i = 1; i <= n; i ++)
        for (int j = 1; j <= v;j ++)
        {
            dp[i][j] = dp[i - 1][j];
            if (j >= a[i].first)
                dp[i][j] = max(dp[i][j], dp[i - 1][j - a[i].first] + a[i].second);
        }
    cout << dp[n][v];
    return 0;
}

滚动数组优化版

#include <bits/stdc++.h>
using namespace std;

const int N = 1e3 + 10;
int dp[2][N] = {0};

int main()
{
    int n, v;
    cin >> n >> v;
    vector<pair<int, int>> a(n + 1);
    for (int i = 1; i <= n; i ++)
        cin >> a[i].first >> a[i].second;
    
    int pre = 1, now = 0;
    for (int i = 1; i <= n; i ++)
    {
        swap(pre, now);
        for (int j = 1; j <= v;j ++)
        {
            dp[now][j] = dp[pre][j];
            if (j >= a[i].first)
                dp[now][j] = max(dp[now][j], dp[pre][j - a[i].first] + a[i].second);
        }
    }
    cout << dp[now][v];
    return 0;
}

一维数组优化版

#include <bits/stdc++.h>
using namespace std;

const int N = 1e3 + 10;
int dp[N] = {0};

int main()
{
    int n, v;
    cin >> n >> v;
    vector<pair<int, int>> a(n + 1);
    for (int i = 1; i <= n; i ++)
        cin >> a[i].first >> a[i].second;
    for (int i = 1; i <= n; i ++)
        for (int j = v; j >= a[i].first;j --)
            dp[j] = max(dp[j], dp[j - a[i].first] + a[i].second);
    cout << dp[v];
    return 0;
}

完全背包

题目描述

有 $N$ 种物品和一个容量是 $V$ 的背包，每种物品都有无限件可用。

第 $i$ 种物品的体积是 $v_i$，价值是 $w_i$。

求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
输出最大价值。

输入格式

第一行两个整数，$N，V$，用空格隔开，分别表示物品种数和背包容积。

接下来有 $N$ 行，每行两个整数 $v_i, w_i$，用空格隔开，分别表示第 $i$ 种物品的体积和价值。

输出格式

输出一个整数，表示最大价值。

数据范围

$0 \lt N, V \le 1000$
$0 \lt v_i, w_i \le 1000$

输入样例

4 5
1 2
2 4
3 4
4 5

输出样例：

10

CODE

二维数组暴力版

#include <bits/stdc++.h>
using namespace std;

const int N = 1e3 + 10;
int dp[N][N];

int main()
{
    int n, v;
    cin >> n >> v;
    vector<pair<int, int>> a(n);
    for (int i = 1; i <= n; i ++)
        cin >> a[i].first >> a[i].second;
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= v; j ++)
            for (int k = 0; k * a[i].first <= j; k ++)
                dp[i][j] = max(dp[i][j], dp[i - 1][j - k * a[i].first] + k * a[i].second);
    cout << dp[n][v];
} 

二维数组常规版

#include <bits/stdc++.h> 
using namespace std;

const int N = 1e3 + 10;
int dp[N][N];

int main()
{
    int n, v;
    cin >> n >> v;
    vector<pair<int, int>> a(n);
    for (int i = 1; i <= n; i ++)
        cin >> a[i].first >> a[i].second;
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= v; j ++)
        {
            dp[i][j] = dp[i - 1][j];
            if (j >= a[i].first)
                dp[i][j] = max(dp[i][j], dp[i][j - a[i].first] + a[i].second);
        }
    cout << dp[n][v];
}

滚动数组优化版

#include <bits/stdc++.h>
using namespace std;

const int N = 1e3 + 10;
int dp[2][N];

int main()
{
    int n, v;
    cin >> n >> v;
    vector<pair<int, int>> a(n);
    for (int i = 1; i <= n; i ++)
        cin >> a[i].first >> a[i].second;
    
    int pre = 1, now = 0;
    for (int i = 1; i <= n; i ++ )
    {
        swap(pre, now);
        for (int j = 1; j <= v; j ++)
        {
            dp[now][j] = dp[pre][j];
            if (j >= a[i].first)
                dp[now][j] = max(dp[now][j], dp[now][j - a[i].first] + a[i].second);
        }
    }
    cout << dp[now][v];
}

一维数组优化版

#include <bits/stdc++.h>
using namespace std;

const int N = 1e3 + 10;
int dp[N];

int main()
{
    int n, v;
    cin >> n >> v;
    vector<pair<int, int>> a(n);
    for (int i = 1; i <= n; i ++)
        cin >> a[i].first >> a[i].second;
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= v; j ++)
        {
            dp[i][j] = dp[i - 1][j];
            if (j >= a[i].first)
                dp[i][j] = max(dp[i][j], dp[i][j - a[i].first] + a[i].second);
        }
    cout << dp[v];
}

混合背包

题目描述

有 $N$ 种物品和一个容量是 $V$ 的背包。

物品一共有三类：

• 第一类物品只能用1次（01背包）；
• 第二类物品可以用无限次（完全背包）；
• 第三类物品最多只能用 $s_i$ 次（多重背包）；

每种体积是 $v_i$，价值是 $w_i$。

求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。
输出最大价值。

输入格式

第一行两个整数，$N，V$，用空格隔开，分别表示物品种数和背包容积。

接下来有 $N$ 行，每行三个整数 $v_i, w_i, s_i$，用空格隔开，分别表示第 $i$ 种物品的体积、价值和数量。

• $s_i = -1$ 表示第 $i$ 种物品只能用1次；
• $s_i = 0$ 表示第 $i$ 种物品可以用无限次；
• $s_i >0$ 表示第 $i$ 种物品可以使用 $s_i$ 次；

输出格式

输出一个整数，表示最大价值。

数据范围

$0 \lt N, V \le 1000$
$0 \lt v_i, w_i \le 1000$
$-1 \le s_i \le 1000$

输入样例

4 5
1 2 -1
2 4 1
3 4 0
4 5 2

输出样例：

8

CODE

#include <bits/stdc++.h>
using namespace std;

const int N = 1e3 + 10;
int dp[N];

int main()
{
    int n, v;
    cin >> n >> v;
    
    vector<array<int, 3>> a;
    for (int i=1;i<=n;i++)
    {
        int x, y, z;
        cin >> x >> y >> z;
        z = abs(z);
        if (z)
        {
            int k = 1;
            while (z >= k)
            {
                a.push_back({k * x, k * y, 1});
                z -= k;
                k <<= 1;
            }
            if (z > 0)  a.push_back({z * x, z * y, 1});
        }
        else
            a.push_back({x, y, z});
    }

    for (auto th : a)
        if (th[2] == 1)
            for (int j=v;j>=th[0];j--)  dp[j] = max(dp[j], dp[j - th[0]] + th[1]);
        else
            for (int j=th[0];j<=v;j++)  dp[j] = max(dp[j], dp[j - th[0]] + th[1]);
    cout << dp[v];
    return 0;
}

多重背包

题目描述

有 $N$ 种物品和一个容量是 $V$ 的背包。

第 $i$ 种物品最多有 $s_i$ 件，每件体积是 $v_i$，价值是 $w_i$。

求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。
输出最大价值。

输入格式

第一行两个整数，$N，V$，用空格隔开，分别表示物品种数和背包容积。

接下来有 $N$ 行，每行三个整数 $v_i, w_i, s_i$，用空格隔开，分别表示第 $i$ 种物品的体积、价值和数量。

输出格式

输出一个整数，表示最大价值。

数据范围

$0 \lt N \le 1000$
$0 \lt V \le 2000$
$0 \lt v_i, w_i, s_i \le 2000$

输入样例

4 5
1 2 3
2 4 1
3 4 3
4 5 2

输出样例：

10

CODE

暴力版

#include <bits/stdc++.h>
using namespace std;

const int N = 110;
int dp[N][N];

int main()
{
    int n, v;
    cin >> n >> v;
    vector<array<int, 3>> a(n + 1);
    for (int i=1;i<=n;i++)
        cin >> a[i][0] >> a[i][1] >> a[i][2];
    
    for (int i = 1; i <= n; i ++)
        for (int j = 1; j <= v; j ++)
            for (int k = 0; k <= a[i][2] && k * a[i][0] <= j; k ++)
                dp[i][j] = max(dp[i][j], dp[i - 1][j - k * a[i][0]] + a[i][1] * k);
    cout << dp[n][v];
    return 0;
}

二进制优化

#include <bits/stdc++.h>
using namespace std;

const int V = 2e3 + 10;
int dp[V];

int main()
{
    int n, v;
    cin >> n >> v;
    vector<pair<int, int>> a;
    a.push_back({0, 0});
    
    for (int i = 1; i <= n; i ++)
    {
        array<int, 3> b;
        cin >> b[0] >> b[1] >> b[2];
        int k = 1;
        while (b[2] >= k)
        {
            a.push_back(make_pair(k * b[0], k * b[1]));
            b[2] -= k;
            k <<= 1;
        }
        if (b[2] > 0)
            a.push_back(make_pair(b[2] * b[0], b[2] * b[1]));
    }
    
    n = a.size();
    for (int i = 1; i <= n; i ++)
        for (int j = v; j >= a[i].first; j --)
                dp[j] = max(dp[j], dp[j - a[i].first] + a[i].second);
    cout << dp[v];
    return 0;
}

二维费用背包

题目描述

有 $N$ 件物品和一个容量是 $V$ 的背包，背包能承受的最大重量是 $M$。

每件物品只能用一次。体积是 $v_i$，重量是 $m_i$，价值是 $w_i$。

求解将哪些物品装入背包，可使物品总体积不超过背包容量，总重量不超过背包可承受的最大重量，且价值总和最大。
输出最大价值。

输入格式

第一行三个整数，$N,V, M$，用空格隔开，分别表示物品件数、背包容积和背包可承受的最大重量。

接下来有 $N$ 行，每行三个整数 $v_i, m_i, w_i$，用空格隔开，分别表示第 $i$ 件物品的体积、重量和价值。

输出格式

输出一个整数，表示最大价值。

数据范围

$0 \lt N \le 1000$
$0 \lt V, M \le 100$
$0 \lt v_i, m_i \le 100$
$0 \lt w_i \le 1000$

输入样例

4 5 6
1 2 3
2 4 4
3 4 5
4 5 6

输出样例：

8

CODE

#include <bits/stdc++.h>
using namespace std;

const int M = 210;
int dp[M][M];

int main()
{
    int n, v, m;
    cin >> n >> v >> m;
    vector<array<int, 3>> a(n + 1);
    for (int i=1;i<=n;i++)  cin >> a[i][0] >> a[i][1] >> a[i][2];

    for (int i=1;i<=n;i++)
        for (int j=v;j>=a[i][0];j--)
            for (int k=m;k>=a[i][1];k--)
                dp[j][k] = max(dp[j][k], dp[j - a[i][0]][k - a[i][1]] + a[i][2]);
    cout << dp[v][m];
    return 0;
}

分组背包

题目描述

有 $N$ 组物品和一个容量是 $V$ 的背包。

每组物品有若干个，同一组内的物品最多只能选一个。
每件物品的体积是 $v_{ij}$，价值是 $w_{ij}$，其中 $i$ 是组号，$j$ 是组内编号。

求解将哪些物品装入背包，可使物品总体积不超过背包容量，且总价值最大。

输出最大价值。

输入格式

第一行有两个整数 $N，V$，用空格隔开，分别表示物品组数和背包容量。

接下来有 $N$ 组数据：

• 每组数据第一行有一个整数 $S_i$，表示第 $i$ 个物品组的物品数量；
• 每组数据接下来有 $S_i$ 行，每行有两个整数 $v_{ij}, w_{ij}$，用空格隔开，分别表示第 $i$ 个物品组的第 $j$ 个物品的体积和价值；

输出格式

输出一个整数，表示最大价值。

数据范围

$0 \lt N, V \le 100$
$0 \lt S_i \le 100$
$0 \lt v_{ij}, w_{ij} \le 100$

输入样例

3 5
2
1 2
2 4
1
3 4
1
4 5

输出样例：

8

CODE

#include <bits/stdc++.h>
using namespace std;

const int N = 120;
int dp[N];

int main()
{
    int n, v, t, x, y;
    cin >> n >> v;
    vector<vector<pair<int, int>>> a(n + 1);
    for (int i = 1; i <= n; i ++)
    {
        cin >> t;
        while (t --)
        {
            cin >> x >> y;
            a[i].push_back(make_pair(x, y));
        }
    }
    
    for (int i = 1; i <= n; i ++)
        for (int j = v; j >= 0; j --)   // 从后往前遍历所有可能体积
            for (int k = 0; k < (int)a[i].size(); k ++)
                if (j >= a[i][k].first)
                    dp[j] = max(dp[j], dp[j - a[i][k].first] + a[i][k].second);
    cout << dp[v];
    return 0;
}

有附属（依赖）背包

题目描述

金明今天很开心，家里购置的新房就要领钥匙了，新房里有一间金明自己专用的很宽敞的房间。更让他高兴的是，妈妈昨天对他说：“你的房间需要购买哪些物品，怎么布置，你说了算，只要不超过 $n$ 元钱就行”。今天一早，金明就开始做预算了，他把想买的物品分为两类：主件与附件，附件是从属于某个主件的，下表就是一些主件与附件的例子：

主件	附件
电脑	打印机，扫描仪
书柜	图书
书桌	台灯，文具
工作椅	无

如果要买归类为附件的物品，必须先买该附件所属的主件。每个主件可以有 $0$ 个、$1$ 个或 $2$ 个附件。每个附件对应一个主件，附件不再有从属于自己的附件。金明想买的东西很多，肯定会超过妈妈限定的 $n$ 元。于是，他把每件物品规定了一个重要度，分为 $5$ 等：用整数 $1 \sim 5$ 表示，第 $5$ 等最重要。他还从因特网上查到了每件物品的价格（都是 $10$ 元的整数倍）。他希望在不超过 $n$ 元的前提下，使每件物品的价格与重要度的乘积的总和最大。

设第 $j$ 件物品的价格为 $v_j$，重要度为 $w_j$，共选中了 $k$ 件物品，编号依次为 $j_1,j_2,\dots,j_k$，则所求的总和为：

$$v_{j_1} \times w_{j_1}+v_{j_2} \times w_{j_2}+ \dots +v_{j_k} \times w_{j_k}$$

请你帮助金明设计一个满足要求的购物单。

输入格式

第一行有两个整数，分别表示总钱数 $n$ 和希望购买的物品个数 $m$。

第 $2$ 到第 $(m + 1)$ 行，每行三个整数，第 $(i + 1)$ 行的整数 $v_i$，$p_i$，$q_i$ 分别表示第 $i$ 件物品的价格、重要度以及它对应的的主件。如果 $q_i=0$，表示该物品本身是主件。

输出格式

输出一行一个整数表示答案。

样例输入

1000 5
800 2 0
400 5 1
300 5 1
400 3 0
500 2 0

样例输出

2200

提示

对于全部的测试点，保证 $1 \leq n \leq 3.2 \times 10^4$，$1 \leq m \leq 60$，$0 \leq v_i \leq 10^4$，$1 \leq p_i \leq 5$，$0 \leq q_i \leq m$，答案不超过 $2 \times 10^5$。

NOIP 2006 提高组 第二题

CODE

struct node
{
    int val, imp;
    vector<int> son;
};

void solve()
{
    int n, m, k;   cin >> n >> m;
    n /= 10;
    vector<int> fa;
    vector<node> goods(m);
    for (int i=0;i<m;i++)
    {
        cin >> goods[i].val >> goods[i].imp >> k;
        goods[i].val /= 10;
        goods[i].imp *= goods[i].val;
        if (k)
            goods[k - 1].son.push_back(i);
        else
            fa.push_back(i);
    }

    vector<int> dp(n + 10, 0);
    for (auto f : fa)
    {
        for (int j=n;j>=goods[f].val;j--)
        {
            dp[j] = max(dp[j], dp[j - goods[f].val] + goods[f].imp);
            for (auto s : goods[f].son)
                if (j - goods[f].val >= goods[s].val)
                    dp[j] = max(dp[j], dp[j - goods[f].val - goods[s].val] + goods[f].imp + goods[s].imp);
            if (goods[f].son.size() == 2)
            {
                int a = goods[f].son[0], b = goods[f].son[1];
                if (j - goods[f].val >= goods[a].val + goods[b].val)
                    dp[j] = max(dp[j], dp[j - goods[f].val - goods[a].val - goods[b].val] + goods[f].imp + goods[a].imp + goods[b].imp);
            }

        }
    }
    cout << dp[n] * 10;
}

背包方案数

题目描述

有 $N$ 件物品和一个容量是 $V$ 的背包。每件物品只能使用一次。

第 $i$ 件物品的体积是 $v_i$，价值是 $w_i$。

求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。

输出 最优选法的方案数。注意答案可能很大，请输出答案模 $10^9 + 7$ 的结果。

输入格式

第一行两个整数，$N，V$，用空格隔开，分别表示物品数量和背包容积。

接下来有 $N$ 行，每行两个整数 $v_i, w_i$，用空格隔开，分别表示第 $i$ 件物品的体积和价值。

输出格式

输出一个整数，表示 方案数 模 $10^9 + 7$ 的结果。

数据范围

$0 \lt N, V \le 1000$
$0\lt v_i, w_i \le 1000$

输入样例

4 5
1 2
2 4
3 4
4 6

输出样例：

2

CODE

#include <bits/stdc++.h>
#define inf 0x3f3f3f3f
using namespace std;

const int MOD = 1e9 + 7;
const int N = 1e3 + 10;
int dp[N], g[N];

int main()
{
    int n, v;
    cin >> n >> v;
    memset(dp, -inf, sizeof dp);
    dp[0] = 0, g[0] = 1;
    vector<pair<int, int>> a(n + 1);
    for (int i = 1;i <= n; i ++)
        cin >> a[i].first >> a[i].second;
        
    for (int i = 1; i <= n; i ++)
    {
        for (int j = v; j >= a[i].first; j --)
        {
            int t = max(dp[j], dp[j - a[i].first] + a[i].second);
            int s = 0;
            if (t == dp[j]) s += g[j];
            if (t == dp[j - a[i].first] + a[i].second)  s += g[j - a[i].first];
            dp[j] = t;
            g[j] = s % MOD;
        }
    }
    
    int mx = -1, ans = 0;
    for (int i = 0; i <= v; i ++)
        mx = max(mx, dp[i]);
    
    for (int i = 0; i <= v; i ++)
        if (dp[i] == mx)
            ans = (ans + g[i]) % MOD;
    cout << ans;
    return 0;
}

背包问题求具体方案

题目描述

有 $N$ 件物品和一个容量是 $V$ 的背包。每件物品只能使用一次。

第 $i$ 件物品的体积是 $v_i$，价值是 $w_i$。

求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。

输出 字典序最小的方案。这里的字典序是指：所选物品的编号所构成的序列。物品的编号范围是 $1 … N$。

输入格式

第一行两个整数，$N，V$，用空格隔开，分别表示物品数量和背包容积。

接下来有 $N$ 行，每行两个整数 $v_i, w_i$，用空格隔开，分别表示第 $i$ 件物品的体积和价值。

输出格式

输出一行，包含若干个用空格隔开的整数，表示最优解中所选物品的编号序列，且该编号序列的字典序最小。

物品编号范围是 $1 … N$。

数据范围

$0 \lt N, V \le 1000$
$0\lt v_i, w_i \le 1000$

输入样例

4 5
1 2
2 4
3 4
4 6

输出样例：

1 4

CODE

#include <bits/stdc++.h>
using namespace std;

const int N = 1e3 + 10;
int dp[N][N];

int main()
{
    int n, v;
    cin >> n >> v;
    vector<pair<int, int>> a(n + 1);
    for (int i = 1; i <= n; i ++)
        cin >> a[i].first >> a[i].second;
    
    for (int i = n; i > 0; i --)
        for (int j = 1; j <= v; j ++)
        {
            dp[i][j] = dp[i + 1][j];
            if (j >= a[i].first)
                dp[i][j] = max(dp[i][j], dp[i + 1][j - a[i].first] + a[i].second);
        }
    
    int i = 1, j = v;
    while (i <= n)
    {
        if (j >= a[i].first && dp[i + 1][j - a[i].first] + a[i].second >= dp[i][j])
        {
            cout << i << " ";
            j -= a[i].first;
            i ++;
        }
        else
            i ++;
	}
}