背包问题
背包问题
01背包问题
问题描述：
有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。
第 i 件物品的体积是 vi，价值是 wi。
求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
数据范围：0<N,V≤1000，0<vi,wi≤1000
解析：
DP问题从两个方面考虑
状态表示：f(i,j)，需要几维来表示状态，每个状态含义
集合：选法的集合；
集合的条件——只从前i个物品中选，总体积<=j
属性：最大值（背包问题中的属性就是最大值）；最小值；数量
状态计算：如何一步步把每一个状态算出来
集合的划分：
不重不漏的分为两类：选法中包含i物品/不包含i物品
1.体积不超过j，前i个物品中不包含i：f(i-1,j)
2.体积不超过j，前i个物品中包含i，f(i-1,j-$v_i$)+$w_i$
代码：
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
| #include<iostream>
#include<cstdio>
using namespace std;
const int N=1020;
int f[N][N];
int v[N],w[N];
int n,m;
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=1;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]);
}
}
cout<<f[n][m];
return 0;
}
for(int i=1;i<=n;i++)
{
for(int j=m;j>=v[i];j--)
{
f[j]=max(f[j],f[j-v[i]]+w[i]);
}
}
|
完全背包问题
问题描述：
有 N 件物品和一个容量是 V 的背包。每种物品都有无限件可用。
第 i 件物品的体积是 vi，价值是 wi。
求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
数据范围：0<N,V≤1000，0<vi,wi≤1000
解析：完全背包问题与01背包很像，状态表示与01背包相同，而集合的划分与01背包有所区别，不再是刚刚好不重不漏的分为两组，而要考虑第i个物品选k个。
选0个（不选）：f(i-1,j)
选k个：f(i-1,j-k*v[i])+w[i]*k
朴素做法代码：
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<cstdio>
using namespace std;
const int N=1020;
int f[N][N];
int v[N],w[N];
int n,m;
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++)
{
for(int k=0;k*v[i]<=j;k++)
{
f[i][j]=max(f[i][j],f[i-1][j-k*v[i]]+k*w[i]);
}
}
}
cout<<f[n][m];
return 0;
}
|
考虑优化，分析状态转移方程：
f(i,j)=max{ f(i-1,j) , f(i-1,j-v)+w , f(i-1,j-2v)+2w,…}
f(i,j-v)=max{ f(i-1,j-v) , f(i-1,j-2v)+w , f(i-1,j-3v)+2w,…}
注意到f(i,j)的很多状态和f(i,j-v)的相同，因此可以很容易发现不需要枚举k，状态转移方程改为：
f(i,j)=max{ f(i-1,j), f(i,j-v)+w }
优化后代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| 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][j-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]);
}
}
|
多重背包问题
问题描述：
有 N 件物品和一个容量是 V 的背包。
第 i 件物品最多有 si 件，每件体积是 vi，价值是 wi。
求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
数据范围：0<N,V≤1000，0<vi,wi,si≤100
解析：朴素版参考完全背包处的分析
代码：
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
| #include<iostream>
#include<cstdio>
using namespace std;
const int N=1020;
int f[N][N];
int v[N],w[N],s[N];
int n,m;
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
{
cin>>v[i]>>w[i]>>s[i];
}
for(int i=1;i<=n;i++)
{
for(int j=0;j<=m;j++)
{
for(int k=0;k<=s[i] and k*v[i]<=j;k++)
{
f[i][j]=max(f[i][j],f[i-1][j-k*v[i]]+k*w[i]);
}
}
}
cout<<f[n][m];
return 0;
}
|
题目不变，更新数据范围
0<N≤1000，0<V≤2000，0<vi,wi,si≤2000
数据强化后，n^3显然会超时。如何优化？
考虑优化，分析状态转移方程：
f(i,j)=max{ f(i-1,j) , f(i-1,j-v)+w,… , f(i-1,j-sv)+sw}
f(i,j-v)=max{ f(i-1,j-v) , f(i-1,j-2v)+w , …,f(i-1,j-sv)+(s-1)w, f(i-1,j-(s+1)v)+sw }
发现f(i,j-v)除了多了最后一项之外都和f(i,j)一样，那么如何求除去最后一项的f(i,j-v)的最大值呢？似乎有点难…
二进制优化：把每种物品打包成：1,2,4,8,…,$2^n$个为一组（$2^n$<=s[i]，剩下的拿s[i]-$(2^n-1)$=c作为最后一组）s个物品就拆成了 logs 个物品，再对这logs个做01背包即可。这logs个物品选下来将会包含s个物品的所有选法！
代码：
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
| #include<iostream>
#include<cstdio>
using namespace std;
const int N=25000,M=2010;
int n,m;
int v[N],w[N],f[N];
int cnt=0;
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
{
int a,b,s;
cin>>a>>b>>s;
int k=1;
while(k<=s)
{
v[++cnt]=a*k;
w[cnt]=b*k;
s-=k;
k*=2;
}
if(s>0)
{
v[++cnt]=a*s;
w[cnt]=b*s;
}
}
n=cnt;
for(int i=1;i<=n;i++)
{
for(int j=m;j>=v[i];j--)
{
f[j]=max(f[j],f[j-v[i]]+w[i]);
}
}
cout<<f[m];
return 0;
}
|
分组背包问题
有 N 组物品和一个容量是 V 的背包。
每组物品有若干个，同一组内的物品最多只能选一个。
每件物品的体积是 v_ij，价值是 w_ij，其中 i 是组号，j 是组内编号。
求解将哪些物品装入背包，可使物品总体积不超过背包容量，且总价值最大。
0<N,V≤100, 0<Si≤100, 0<vij,wij≤100
解析：
状态表示：
集合：只从前i组物品中选，总体积不大于j的所有选法
属性：选法中总价值的最大值
状态计算：完全背包/多重背包：第i组物品选几个
分组背包：第i组物品选哪个——只有一个选（联想到01背包）
不选：f(i-1,j) 选第k个：f(i-1,j-v[i,k])+w[i,k];
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
| #include<iostream>
#include<cstdio>
using namespace std;
const int N=150;
int n,m;
int v[N][N],w[N][N];
int s[N],f[N][N];
int main()
{
ios::sync_with_stdio(0);
cin>>n>>m;
for(int i=1;i<=n;i++)
{
cin>>s[i];
for(int j=1;j<=s[i];j++)
{
cin>>v[i][j]>>w[i][j];
}
}
for(int i=1;i<=n;i++)
{
for(int j=0;j<=m;j++)
{
f[i][j]=f[i-1][j];
for(int k=1;k<=s[i];k++)
{
if(v[i][k]<=j)
{
f[i][j]=max(f[i][j],f[i-1][j-v[i][k]]+w[i][k]);
}
}
}
}
cout<<f[n][m];
return 0;
}
for(int i=1;i<=n;i++)
{
for(int j=m;j>=0;j--)
{
for(int k=1;k<=s[i];k++)
{
if(v[i][k]<=j)
{
f[j]=max(f[j],f[j-v[i][k]]+w[i][k]);
}
}
}
}
|