背包问题
01背包
有$ N $件物品和一个容量是 $V $的背包。每件物品只能使用一次。
第 $i$ 件物品的体积是 $v_i$，价值是 $w_i$。
求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
输出最大价值。
Tips: 这个是最基础的背包问题。 背包问题属于动态规划的一种， $f[i] $表示体积为 $i $背包的最大的价值。那么转移方程就比较简单了，对于物品(v, w) 有选和不选两种方案。
$ f[i] =max( f[i], f[i-v] +w) $ 这样的式子就是比较nice的选择。 01 背包问题的体积是从大到小进行枚举的。
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
|
// 01 背包问题， f[i] =max(f[i], f[i -w]+ v)
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N= 1010;
int f[N];
int v[N], w[N];
int n, m;
int main()
{
cin>> n>> m;
for(int i =0; i< n; i++)
{
int v, w;
cin >> v>> w;
for (int j =m ; j>=v; j--)
f[j] =max(f[j], f[j -v]+w );
}
cout << f[m]<<endl;
return 0;
}
|
使用 n 个数字表示总和为 m 的总共的情况数。 n 表示从 1 到n 的数字。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
# 这个是一个 01 背包问题， dp[i][j] 表示使用前 i 个数字表示总和为 j 的情况
# 对于数字 i 有两种选法：选或者不选
def solution(n, m):
p = [i for i in range(n+1)]
dp = [[0] * (m+1) for _ in range(n +1)]
# 初始化
for i in range(n):
dp[i][0] =1
for i in range(1,m):
dp[0][i] =0
for i in range(1, n+1):
for j in range(m+1):
if p[i] <= j:
dp[i][j] = dp[i-1][j] + dp[i-1][j -p[i]]
else:
dp[i][j] = dp[i-1][j]
return dp[n][m]
|
完全背包问题
有$ N $件物品和一个容量是 $V $的背包。每件物品都有无限件可用。
第 $i$ 件物品的体积是 $v_i$，价值是 $w_i$。
求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
输出最大价值。
Tips： 这个跟上面的不同点在于，物品是无限件可用，01 背包是只能用一个。从代码实现上看， 01背包问题的 体积是从大到小遍历的，然后完全背包问题是从小到大遍历的。
01 背包问题和 完全背包问题的区别在于前者物品只有选择与否两种方案。而完全背包对于每件物品有无限件可以选择。对于体积v 是从小到大进行枚举的。
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
|
// 转移方程 f[i] =max(f[i], f[i -v]+w) 没有变，实现的时候有差别
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N =1010;
int f[N];
int n, m;
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++) // 注意这个是 <= 号; 这个起始点是假设放入了体积为v 的物品
f[j] =max(f[j], f[j -v]+w);
}
cout<< f[m]<<endl;
return 0;
}
|
多重背包问题 1
有$ N $件物品和一个容量是 $V $的背包。每件物品都有无限件可用。
第 $i$ 件物品最多有 $s_i$ 件, 每件体积是 $v_i$，价值是 $w_i$。
求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
输出最大价值。
$$
\begin{split}
0< & N \leq 100 \\
0< & V \leq 100 \\
0< & v_{i}, w_{i}, s_{i} \leq 100
\end{split}
$$
Tips： 多重背包问题是转换成 01 背包问题进行解决的，这个大的思路是没有问题的。只是对于不同的数据规模有两种不同的实现手段。当数据规模比较小的时候，三重循环就搞定了；当数据规模比较大的时候，需要使用一个结构体进行操作。
（多重背包问题对物品的个数进行了限制，不是无限个，转换成01 背包问题，体积是从大到小进行枚举）
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
|
#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>=0; 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;
}
|
多重背包问题 2
有$ N $件物品和一个容量是 $V $的背包。每件物品都有无限件可用。
第 $i$ 件物品最多有 $s_i$ 件, 每件体积是 $v_i$，价值是 $w_i$。
求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
输出最大价值。
数据范围:
$$
\begin{split}
0< & N \leq 1000 \\
0< & V \leq 2000 \\
0< & v_{i}, w_{i}, s_{i} \leq 2000
\end{split}
$$
Tips: 主要区别在于数据的维度。 这个是转换成 成 01 背包问题，上一道题目是在 01 背包问题的基础上（框架上）进行修改。 这个从时间复杂度上的优化：$1000 \times 2000 \times 2000$ -> $1000 \times 2000 \times \log(2000) $ 。经过优化 基本上在 $ 10^7 $，所以这个速度是可以接受的。 c++ 在 1s 中就是可以计算 $10^7 $ 这样运算。
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
|
#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
const int N =2010 ; // 这个数量是 v的最大值
int f[N];
int n, m;
struct Good{
int v, w;
};
vector<Good> goods;
int main()
{
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;
goods.push_back({v*k, w*k});
}
if(s >0) goods.push_back({v*s, w*s});
}
// 01 hnapsack
// goods 的长度不一定是 n， 所以不能这样进行遍历
/*
for(int i =0; i<n; i++)// 这个
for(int j =m ; j>= goods[i].v; j--)
{
f[j] =max(f[j], f[j -goods[i].v] +goods[i].w);
}
*/
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;
}
|
混合背包问题
有 $ N$种物品和一个容量是 $V$的背包。
物品一共有三类：
- 第一类物品只能用1次（01背包）；
- 第二类物品可以用无限次（完全背包）；
- 第三类物品最多只能用 $s_i $次（多重背包）；
每种体积是 $v_i$，价值是 $w_i$。
求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。
输出最大价值。
Tips： 分类讨论，多重背包问题转成 01背包问题，所以最后是有两类。
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
|
#include<iostream>
#include<algorithm>
#include<vector>
#include<cstring>
using namespace std;
/*
分成两类： 01 背包问题和完全背包问题；对于多重背包问题使用 二进制进行优化，得到01 背包问题。
所以需要一个新的结构体
01 背包问题只有两个循环，一个是物品的循环，一个是商品的循环
*/
const int N =1010;
int f[N];
int n, m;
struct Thing
{
int v, w, s;
};
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 ==-1) things.push_back({v, w, -1});
else if (s ==0) things.push_back({v, w, 0});
else
{
for(int k =1; k<=s; k *=2)
{
s -=k;
things.push_back({v*k, w*k, -1});
}
if (s >0) things.push_back({v*s, w*s, -1});
}
}
// 01 背包问题
for(auto thing: things)
{
if(thing.s ==-1)
{
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;
}
|
二维费用的背包问题
有 N 件物品和一个容量是 V 的背包，背包能承受的最大重量是 M。
每件物品只能用一次。体积是$ v_i$， 重量是 $m_i$，价值是$ w_i$。
求解将哪些物品装入背包，可使物品总体积不超过背包容量，总重量不超过背包可承受的最大重量，且价值总和最大。
输出最大价值。
Tips: 一般来说背包问题只有一个限制条件：V。但是这种是可以扩展到多维，即有多个限制条件，比如重量。很简单的扩展是加上一个循环。同理 f 这样的函数是可以扩展成二维的。
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
|
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N =1010;
int f[N][N];
int n,v, m;
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;
}
|