背包

一、01背包

对前i个物品，都有选或不选的01状态。

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

二、完全背包问题

每种物品可无限取用。

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

三、多重背包问题

每种物品有限取。

(一)二进制优化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
for(int i=1; i<=n; i++)
{
  int k=1, a,b,s; cin>>a>>b>>s;
  while(k<=s)
  {
    cnt++;
    v[cnt]=k*a; w[cnt]=k*b;
    s-=k; k*=2;
  }
  if(s>0)
  {
    cnt++;
    v[cnt]=s*a; w[cnt]=s*b;
  }
}
n=cnt;
for(int i=1; i<=n; i++)
  for(int j=m; j>=v[i]; j--)
    dp[j]=max(dp[j], dp[j-v[i]]+w[i]);

cout<<dp[m];

(三)单调队列优化

三、混合背包

  • 第一类物品只能用1次（01背包）；

  • 第二类物品可以用无限次（完全背包）；

  • 第三类物品最多只能用 $S_i$次（多重背包）；

1
2
3
if(s<0) s=1;
else if(s==0) s=m/a;
//之后多重背包模板

将混合背包转化位多重背包问题。

四、二维背包

有两个限制，设置二维数组，两层遍历。

1
2
3
4
5
for(int i=1; i<=n; i++)
  for(int j=V; j>=v[i]; j++)
    for(int k=M; k>=m[i]; k++)
      dp[j][k]=max(dp[j][k], dp[j-v[i]][k-m[i]]+w[i]);
cout<<dp[V][M];

五、分组背包

物品分为n组，每组只能选一个。

1
2
3
4
for(int i=1; i<=n; i++)
  for(int j=m; j>=1; j--)
    for(int k=1; k>=s[i]; k++)
      if(v[i][k]<=j) dp[j]=max(dp[j], dp[j-v[i][k]]+w[i][k]);