背包九讲专题

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

01背包问题

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

第 i件物品的体积是 vi，价值是 wi。

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

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

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

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

数据范围
0<N,V≤1000
0<vi,wi≤1000

输入样例
4 5
1 2
2 4
3 4
4 5

输出样例：
8

/*

f[i][j] 表示只看前i个物品，总体积是j的情况下，总价值最大是多少

result = max(f[n][0 ~ v])

f[i][j]:

1.不选第i个物品, f[i][j] = f[i - 1][j];
2.选第i 个物品,  f[i][j] = f[i - 1][j - v[i]];

f[i][j] = max(1, 2)

f[0][0] = 0;

*/

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

using namespace std;

const int N = 1010;

int n, m;
int f[N][N];
int v[N], w[N]; //体积 价值

int main()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i++) cin >> 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];//不选
            if(j >= v[i])
                f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + w[i]);//选
        }
    int res = 0;
    for(int i = 0; i <= m; i++) res = max(res, f[n][i]);
    
    cout << res << endl;
    return 0;
}

优化

/*

f[i][j] 表示只看前i个物品，总体积是j的情况下，总价值最大是多少

result = max(f[n][0 ~ v])

f[i][j]:

1.不选第i个物品, f[i][j] = f[i - 1][j];
2.选第i 个物品,  f[i][j] = f[i - 1][j - v[i]];

f[i][j] = max(1, 2)

f[0][0] = 0;

*/

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

using namespace std;

const int N = 1010;

int n, m;
int f[N]; //优化1 把二维数组变成一维数组 体积是i的时候最大价值是多少
int v[N], w[N]; //体积 价值

int main()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i++) cin >> v[i] >> w[i];
    
    for(int i = 1; i <= n; i++)
        for(int j = m; j >= v[i]; j--) //从大到小枚举 保证下面算的时候 是 i-1 不是 i
                f[j] = max(f[j], f[j - v[i]] + w[i]);//选
   
    cout << f[m] << endl; //优化2 f[m]
    return 0;
}

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14
• 15
• 16
• 17
• 18
• 19
• 20
• 21
• 22
• 23
• 24
• 25
• 26
• 27
• 28
• 29
• 30
• 31
• 32
• 33
• 34
• 35
• 36
• 37
• 38
• 39
• 40
• 41
• 42
• 43
• 44
• 45
• 46
• 47
• 48
• 49
• 50
• 51
• 52
• 53
• 54
• 55
• 56
• 57
• 58
• 59
• 60
• 61
• 62
• 63
• 64
• 65
• 66
• 67
• 68
• 69
• 70
• 71
• 72
• 73
• 74
• 75
• 76
• 77
• 78
• 79
• 80
• 81
• 82
• 83
• 84
• 85
• 86
• 87
• 88
• 89
• 90
• 91

完全背包问题

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

第 i种物品的体积是 vi，价值是 wi。

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

输入格式

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

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

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

数据范围
0<N,V≤1000
0<vi,wi≤1000

输入样例
4 5
1 2
2 4
3 4
4 5

输出样例：
10

/*

f[i] 表示 总体积是i的情况下，最大价值是多少

result = max(f[0 ... m)

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

*/

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

using namespace std;

const int N = 1010;

int n, m;
int f[N];

int main()
{
    cin >> n >> m;
    for(int i = 0; i < n; i ++)
    {
        int v, w;
        cin >> v >> w;
        for(int j = v; j <= m; j++)
            f[j] = max(f[j], f[j - v] + w);
    }
    
    cout << f[m] <<endl;
    return 0;
}

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14
• 15
• 16
• 17
• 18
• 19
• 20
• 21
• 22
• 23
• 24
• 25
• 26
• 27
• 28
• 29
• 30
• 31
• 32
• 33
• 34
• 35
• 36
• 37
• 38
• 39
• 40
• 41
• 42
• 43

小结 ！！！

01背包：每件物品只能用一次 第一重循环循环物品 第二重循环体积从大到小枚举
完全背包：每件物品能用无限次 第一重循环不变 第二重循环从小到大枚举

多重背包问题 I

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

第 i种物品最多有 si 件，每件体积是 vi，价值是 wi。

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

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

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

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

数据范围
0<N,V≤100
0<vi,wi,si≤100

输入样例
4 5
1 2 3
2 4 1
3 4 3
4 5 2

输出样例：
10

/*

f[i] 总体积是i的情况下，最大价值是多少

for(int i = 0; i < n; i++)
{
    for(int j = m; j >= v[i]; j --)
        f[j] = max(f[j], f[j - v[i] + w[i]); 01背包
        f[j] = max(f[j], f[j - v[i] + w[i], f[j - 2 * v[i] + 2 * w[i] ...); 选多个 01背包的拓展 也要从大到小枚举
}

1. f[i] = 0 都已经初始化
f[m]

[0] = 0  f[i] = -INF, i != 0;
max(f[0 ... m]) 枚举所有 求最大值

*/

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

using namespace std;

const int N = 110;

int n, m;
int f[N];

int main()
{
    cin >> n >> m;
    for(int i = 0; i < n; i++)
    {
        int v, w, s;
        cin >> v >> w >> s;
        for(int j = m; j >= v; j--) //从大到小枚举
            for(int k = 1; k <= s && k * v <= j; k ++)
                f[j] = max(f[j], f[j - k * v] + k * w);
    }
    cout << f[m] << endl;
    return 0;
}

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14
• 15
• 16
• 17
• 18
• 19
• 20
• 21
• 22
• 23
• 24
• 25
• 26
• 27
• 28
• 29
• 30
• 31
• 32
• 33
• 34
• 35
• 36
• 37
• 38
• 39
• 40
• 41
• 42
• 43
• 44

多重背包问题 II

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

第 i种物品最多有 si 件，每件体积是 vi，价值是 wi。

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

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

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

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

数据范围
0<N≤1000
0<V≤2000
0<vi,wi,si≤2000

提示：
本题考查多重背包的二进制优化方法。

输入样例
4 5
1 2 3
2 4 1
3 4 3
4 5 2

输出样例：
10

/*

v w 

s - 1 - 2 - 4 - 8 - ...   s - k的整数幂，直到比k小为止

los(s)

1000 * 11 * 2000 = 2 * 10^7

*/

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

using namespace std;

const int N = 2010;

int n, m;
int f[N];

struct Good
{
    int v, w;
};

int main()
{
    vector<Good> goods;
    cin >> n >> m;
    for(int i = 0; i < n; i++)
    {
        int v, w, s;
        cin >> v >> w >> s;
        for(int k = 1; k <= s; k *= 2)
        {
            s -= k;//s - k的整数幂，直到比k小为止
            goods.push_back({v * k, w * k});
            
        }
        if(s > 0) goods.push_back({v * s, w * s}); //剩余的 加入数组
    }
    
    for(auto good : goods)
        for(int j = m; j >= good.v; j --)
            f[j] = max(f[j], f[j - good.v] + good.w);
            
    cout << f[m] << endl;        
    return 0;
}

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14
• 15
• 16
• 17
• 18
• 19
• 20
• 21
• 22
• 23
• 24
• 25
• 26
• 27
• 28
• 29
• 30
• 31
• 32
• 33
• 34
• 35
• 36
• 37
• 38
• 39
• 40
• 41
• 42
• 43
• 44
• 45
• 46
• 47
• 48
• 49
• 50
• 51
• 52
• 53

多重背包问题 III

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

第 i种物品最多有 si 件，每件体积是 vi，价值是 wi。

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

输入格式
第一行两个整数，N，V(0<N≤1000, 0<V≤20000)，用空格隔开，分别表示物品种数和背包容积。

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

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

数据范围
0<N≤1000
0<V≤20000
0<vi,wi,si≤20000

提示
本题考查多重背包的单调队列优化方法。

输入样例
4 5
1 2 3
2 4 1
3 4 3
4 5 2

输出样例：
10

/*

1000 * log(20000) * 20000 

f[j] = f[j - v] + w, f[j - 2 * v] + 2 * w, ... f[j - k * v] + k * w

f[0]
f[v] - 1 * w
f[2v] - 2 * w

f[j - v] = f[j] + w, f[j - v] + 2 * w

*/

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

using namespace std;

const int N = 20010;

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

int main()
{
    cin >> n >> m;
    for(int i = 0; i < n; i++)
    {
        int v, w, s;
        cin >> 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;
            }
        }
    }
    cout << f[m] << endl;
    return 0;
}

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14
• 15
• 16
• 17
• 18
• 19
• 20
• 21
• 22
• 23
• 24
• 25
• 26
• 27
• 28
• 29
• 30
• 31
• 32
• 33
• 34
• 35
• 36
• 37
• 38
• 39
• 40
• 41
• 42
• 43
• 44
• 45
• 46
• 47
• 48
• 49
• 50
• 51

混合背包问题

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

物品一共有三类：

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

• 1
• 2
• 3

每种体积是 vi，价值是 wi。

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

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

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

si=−1表示第 i种物品只能用1次；
si=0表示第 i种物品可以用无限次；
si>0表示第 i 种物品可以使用 si 次；

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

数据范围
0<N,V≤1000
0<vi,wi≤1000
−1≤si≤1000

输入样例
4 5
1 2 -1
2 4 1
3 4 0
4 5 2

输出样例：
8

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

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()
{
    cin >> n >> m;
    for(int i = 0; i < n; i ++)
    {
        int v, w, s;
        cin >> v >> w >> s;
        if (s < 0) things.push_back({-1, v, w});//s < 0 01背包问题
        else if (s == 0) things.push_back({0, v, w}); // s == 0 完全背包问题
        else //多重背包问题 分成log(s)
        {
            for(int k = 1; k <= s; k *= 2)
            {
                s -= k;
                things.push_back({-1, v * k, w * k});//分成类别是 01背包问题
            }
            if(s > 0) things.push_back({-1, v * s, w * s});
        }
    }
    
    for(auto thing : things)
    { 
        if(thing.kind < 0) //01背包问题 从大到小枚举
        {
            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);
        }
    }
    
    cout << f[m] << endl;
    return 0;
}

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14
• 15
• 16
• 17
• 18
• 19
• 20
• 21
• 22
• 23
• 24
• 25
• 26
• 27
• 28
• 29
• 30
• 31
• 32
• 33
• 34
• 35
• 36
• 37
• 38
• 39
• 40
• 41
• 42
• 43
• 44
• 45
• 46
• 47
• 48
• 49
• 50
• 51
• 52
• 53
• 54

二维费用的背包问题

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

每件物品只能用一次。体积是 vi，重量是 mi，价值是 wi。

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

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

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

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

数据范围
0<N≤1000
0<V,M≤100
0<vi,mi≤100
0<wi≤1000

输入样例
4 5 6
1 2 3
2 4 4
3 4 5
4 5 6

输出样例：
8

/*

f[i][j]

*/

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 110;

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

int main()
{
    cin >> n >> v >> m;
    for(int i = 0; i < n; i++)
    {
        int a, b, c;
        cin >> 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);
    }
    cout << f[v][m] << endl;
    return 0;
}

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14
• 15
• 16
• 17
• 18
• 19
• 20
• 21
• 22
• 23
• 24
• 25
• 26
• 27
• 28
• 29
• 30

分组背包问题

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

每组物品有若干个，同一组内的物品最多只能选一个。
每件物品的体积是 vij，价值是 wij，其中 i 是组号，j是组内编号。

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

输出最大价值。

输入格式
第一行有两个整数 N，V，用空格隔开，分别表示物品组数和背包容量。
接下来有 N组数据：

每组数据第一行有一个整数 Si，表示第 i个物品组的物品数量；
每组数据接下来有 Si行，每行有两个整数 vij,wij，用空格隔开，分别表示第 i 个物品组的第 j 个物品的体积和价值；

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

数据范围
0<N,V≤100
0<Si≤100
0<vij,wij≤100

输入样例
3 5
2
1 2
2 4
1
3 4
1
4 5

输出样例：
8

/*

f[i][j] 前i组 体积是j的情况下 最大价值是多少

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

f[m]

*/

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 110;

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

int main()
{
    cin >> n >> m;
    for(int i = 0; i < n; i++)
    {
        int s;
        cin >> s;
        for(int j = 0; j < s; j++) cin >> v[j] >> w[j];
        for(int j = m; j >= 0; j --) // j >= 0
            for(int k = 0; k < s; k++)
                if(j >= v[k]) //判断 j - v[k] >= 0
                    f[j] = max(f[j], f[j - v[k]] + w[k]);
    }
    cout << f[m] << endl;
    return 0;
}

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14
• 15
• 16
• 17
• 18
• 19
• 20
• 21
• 22
• 23
• 24
• 25
• 26
• 27
• 28
• 29
• 30
• 31
• 32
• 33
• 34
• 35
• 36
• 37
• 38
• 39
• 40

有依赖的背包问题

有 N 个物品和一个容量是 V

的背包。

物品之间具有依赖关系，且依赖关系组成一棵树的形状。如果选择一个物品，则必须选择它的父节点。

如下图所示：

如果选择物品5，则必须选择物品1和2。这是因为2是5的父节点，1是2的父节点。

每件物品的编号是 i，体积是 vi，价值是 wi，依赖的父节点编号是 pi。物品的下标范围是 1…N。

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

输出最大价值。

输入格式

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

接下来有 N行数据，每行数据表示一个物品。
第 i 行有三个整数 vi,wi,pi，用空格隔开，分别表示物品的体积、价值和依赖的物品编号。
如果 pi=−1，表示根节点。 数据保证所有物品构成一棵树。

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

数据范围
1≤N,V≤100
1≤vi,wi≤100

父节点编号范围：
内部结点：1≤pi≤N;
根节点 pi=−1;

输入样例
5 7
2 3 -1
2 2 1
3 5 1
4 7 2
3 6 2

输出样例：
11

/*

f[i][j] 节点i 体积是j 所能选取的最大价值

*/

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

using namespace std;

const int N = 110;

int n, m;
int h[N], e[N], ne[N], idx;
int v[N], w[N], 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 != -1; i = ne[i])
    {
        int son = e[i];
        dfs(son);
        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]);
    }
    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()
{
    memset(h, -1, sizeof h);
    cin >> n >> m;
    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); //父亲为p 儿子为i
    }
    
    dfs(root);
    cout << f[root][m] << endl;
    
    return 0;
}

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14
• 15
• 16
• 17
• 18
• 19
• 20
• 21
• 22
• 23
• 24
• 25
• 26
• 27
• 28
• 29
• 30
• 31
• 32
• 33
• 34
• 35
• 36
• 37
• 38
• 39
• 40
• 41
• 42
• 43
• 44
• 45
• 46
• 47
• 48
• 49
• 50
• 51
• 52
• 53
• 54
• 55

背包问题求方案数

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

第 i件物品的体积是 vi，价值是 wi。

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

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

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

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

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

数据范围
0<N,V≤1000
0<vi,wi≤1000

输入样例
4 5
1 2
2 4
3 4
4 6

输出样例：
2

/*
    f[i] 表示体积恰好是i的体积是多少
    g[i] 表示体积恰好是i的方案数是多少
*/

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

using namespace std;

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

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

int main()
{
    cin >> n >> m;
    g[0] = 1;
    for(int i = 1; i <= m; i++) f[i] = -INF;//初始化
    for(int i = 0; i < n; i++) //先循环物品
    {
        int v, w;
        cin >> 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;
        }
    cout << res << endl;
    return 0;
}

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14
• 15
• 16
• 17
• 18
• 19
• 20
• 21
• 22
• 23
• 24
• 25
• 26
• 27
• 28
• 29
• 30
• 31
• 32
• 33
• 34
• 35
• 36
• 37
• 38
• 39
• 40
• 41
• 42
• 43
• 44
• 45
• 46
• 47
• 48
• 49

背包问题求具体方案

有 N 件物品和一个容量是 V的背包。每件物品只能使用一次。
第 i件物品的体积是 vi，价值是 wi。
求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
输出 字典序最小的方案。这里的字典序是指：所选物品的编号所构成的序列。物品的编号范围是 1…N。

输入格式
第一行两个整数，N，V，用空格隔开，分别表示物品数量和背包容积。
接下来有 N行，每行两个整数 vi,wi，用空格隔开，分别表示第 i件物品的体积和价值。

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

数据范围
0<N,V≤1000
0<vi,wi≤1000

输入样例
4 5
1 2
2 4
3 4
4 6

输出样例：
1 4

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1010;

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

int main()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i ++) cin >> v[i] >> w[i];
    
    for(int i = n; i >= 1; i--)
        for(int j = 0; j <= m; j ++)
        {
            f[i][j] = f[i + 1][j];
            if(j >= v[i]) f[i][j] = max(f[i + 1][j], f[i + 1][j - v[i]] + w[i]);
            
        }
        
    int vol = m;
    for(int i = 1; i <= n; i++)
    {
        if(vol - v[i] >= 0 && f[i][vol] == f[i + 1][vol - v[i]] + w[i]) //相等 说明选了
        {
            cout << i << ' ';
            vol -= v[i];
        }
        
    }
    return 0;
}

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14
• 15
• 16
• 17
• 18
• 19
• 20
• 21
• 22
• 23
• 24
• 25
• 26
• 27
• 28
• 29
• 30
• 31
• 32
• 33
• 34
• 35