【算法】动态规划之背包DP问题（2024.5.11）

 前言：

本系列是学习了董晓老师所讲的知识点做的笔记

董晓算法的个人空间-董晓算法个人主页-哔哩哔哩视频 (bilibili.com)

动态规划系列 

【算法】动态规划之线性DP问题-CSDN博客

01背包

步骤：

分析容量j与w[i]的关系，然后分析是否要放入背包

二维数组

for(int i=1; i<=n; i++)       //物品
    for(int j=1; j<=m; j++)     //容量
      if(j<w[i]) f[i][j]=f[i-1][j];            
      else f[i][j]=max(f[i-1][j],f[i-1][j-w[i]]+c[i]);

一维数组用逆序循环的原因

用一维数组f[i]只记录一行数据，让j值顺序循环，顺序更新f[j]值，f[j-w[i]]会先于f[j]更新，会出错。

如果j是逆序循环，f[j]会先于f[j-w[i]]更新

01背包使用的是上一层的值，如果顺序循环的话就会改变应有的值

for (int i = 1; i <= n; i++)//物品i
{
    for (int j = m; j >= w[i], j--)//容量j
	{
		f[j] = max(f[j], f[j - w[i]] + c[i])
	}
}

完全背包 

完全背包使用的是同一层的值，顺序循环的话改变值正是他所需要的，所以他可以顺序循环

for(int i=1; i<=n; i++)       //物品
    for(int j=1; j<=m; j++)     //容量
      if(j<w[i]) f[i][j]=f[i-1][j];            
      else f[i][j]=max(f[i-1][j],f[i][j-w[i]]+c[i]);

for (int i = 1; i <= n; i++)//物品i
{
    for (int j = w[i]; j <= m, j++)//容量j
	{
		f[j] = max(f[j], f[j - w[i]] + c[i])
	}
}

01背包和完全背包的区别

01背包第i件物品可以放入0个或者1个

完全背包第i件物品可以放入0个，1个，2个..... 

多重背包

01背包:第i种物品可以取0件、取1件。

多重背包:第i种物品可以取0件、取1件、取2件……取s件。

多重背包转化为01背包求解:把第i种物品换成s件01背包中的物品，每件物品的体积为k*v，价值为k*w(0≤k≤s)。

朴素算法

  //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]&&k*v[i]<=j; k++) 
    f[i][j]=max(f[i][j],f[i-1][j-k*v[i]]+k*w[i]);

二进制优化

int num = 1;
for (int i = 1; i <= n; i++)
{
	cin >> v >> w >> s;//体积，价值，数量
	for (j = 1; j <= s; j <<= 1)
	{
		vv[num] = j * v;
		ww[num++] = j * w;
		s -= j;
	}
	if (s)
	{
		vv[num] = s * v;
		ww[num++] = s * w;
	}
}
for (int i = 1; i < num; i++)
	for (int j = m; j >= v[i]; j--)
		f[j] = max(f[j], f[j - vv[i]] + ww[i]);

单调队列

前置知识 

【算法】用存入下标的方法来巧解单调队列-CSDN博客

(k-q[h])/v是还能放入物品的个数。f[k]=窗口中的最大值+还能放入物品的价值。 

混合背包 

题目：

思路

分类处理的思想:
1.利用多重背包的二进制优化，将多重背包转化为多个01背包。
2.用a,b,c三个数组来记录转化之后的所有背包的体积、价值、类型，c[i]==0表示完全背包，c[i]==1表示01背包。最后再做一遍，以c的值分为两类，做完全背包和01背包。

for (int i = 1; i <= n; i++) {
    scanf("%d%d%d", &v, &w, &s);
    if (s == 0) {     //完全背包
        a[num] = v;
        b[num] = w;
        c[num++] = 0; //背包类型 
    }
    else {         
        if (s == -1)
            s = 1;//01背包转多重背包
        int k = 1;
        while (s >= k) {//二进制拆分
            a[num] = k * v;
            b[num] = k * w;
            c[num++] = 1;
            s -= k; k <<= 1;
        }
        if (s) {
            a[num] = s * v;
            b[num] = s * w;
            c[num++] = 1;
        }
    }
}
for (int i = 1; i < num; i++) {
	if (c[i] == 1) //01背包
	     for (int j = m; j >= a[i]; j--)
			f[j] = max(f[j], f[j - a[i]] + b[i]);
	else        //完全背包
		for (int j = a[i]; j <= m; j++)
			f[j] = max(f[j], f[j - a[i]] + b[i]);
}

二维费用背包 

f[i][k]: 背包容量为j，且承重为k时，能放入的最大价值。

f[V][M]: 背包容量为V，且承重为M时能放入的最大价值，即全局最优解。

  cin>>n>>V>>M;
  for(int i=1; i<=n; i++){  //物品 
    cin>>v>>m>>w;
    for(int j=V; j>=v; j--) //体积
    for(int k=M; k>=m; k--) //重量
      f[j][k]=max(f[j][k],f[j-v][k-m]+w);
}
  cout<<f[V][M];

分组背包

分组背包与多重背包的区别是分组背包在每一个组中只能选一个 

决策在前，体积在后的方法是错误的（用同一组的物品来更新了），积前策后才是对的

二维决策：同一个组里面的物品只能选一个

一维决策：个数

for (int i = 1; i <= n; i++)     //物品组
for (int j = 1; j <= V; j++)     //体积
for (int k = 0; k <= s[i]; k++)  //决策
if (j >= v[i][k])
f[i][j] = max(f[i][j], f[i - 1][j - v[i][k]] + w[i][k]);

for (int j = 1; j <= s; j++) 
cin >> v[j] >> w[j];
for (int j = V; j >= 1; j--) //体积
for (int k = 0; k <= s; k++) //决策
if (j >= v[k]) f[j] = max(f[j], f[j - v[k]] + w[k]);