背包问题汇总

01背包 最优解

参考：背包问题中 体积至多是 j ，恰好是 j ，至少是 j 的初始化问题的研究 - AcWing

模板题：蓝桥杯省赛无忧班（C&C++ 组）第 1 期 - 小明的背包1 - 蓝桥云课 (lanqiao.cn)

说明1：如果需要限制取走物品的个数，而不是重量，只需要设每个物品的体积为1，再调整背包体积即可

说明2：如果需要使用LONG LONG，INF可以修改为0x3f3f3f3f3f3f3f3f，但初始化不能用memset，需要遍历DP数组。

1：给n个物品，并给出每个物品的体积w和价值v，背包体积不超过m，求能获得的最大价值。

// 无需进行初始化，DP数组全部为0即可
for(int i = 1 ; i <= n ; i ++){
    for(int j = m ; j >= v[i] ; j --){
        dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
    }
}
cout<<dp[m];

2：给n个物品，并给出每个物品的体积w和价值v，背包体积恰好是m，求能获得的最大价值/最小价值。

1）最大价值

// 保证只有递归回到dp[0]的状态会被考虑
// dp[0] = 0, 其余为-INF
memset(dp, -INF, sizeof(dp));
dp[0] = 0;
for(int i = 1 ; i <= n ; i ++){
    for(int j = m ; j >= v[i] ; j --){
        dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
    }
}
cout<<dp[m];

2）最小价值

// dp[0] = 0, 其余为INF
memset(dp, INF, sizeof(dp));
dp[0] = 0;
for(int i = 1 ; i <= n ; i ++){
    for(int j = m ; j >= v[i] ; j --){
        dp[j] = min(dp[j], dp[j - w[i]] + v[i]);
    }
}
cout<<dp[m];

3：给n个物品，并给出每个物品的体积w和价值v，背包体积至少是m，求能获得的最小价值。

// dp[0] = 0, 其余为INF
memset(dp, INF, sizeof(dp));
dp[0] = 0;
for(int i = 1 ; i <= n ; i ++){
    for(int j = m ; j >= 0 ; j --){
        // 即使，j - w[i]
        dp[j] = min(dp[j], dp[max(0, j - w[i])] + v[i]);
    }
}
cout<<dp[m];

01背包 方案数

1：给n个物品，每个物品的体积为v，且只能选一次，求总体积不超过m的方案数

二维

//对于方案数问题，二维数组的好处是, dp{i, j}能够表示取前i个物品，体积不超过j的方案数。
for(int i = 0 ; i <= m ; i ++){
    dp[0][i] = 1;
}

for(int i = 1 ; i <= n ; i ++){
    for(int j = m ; j >= 0 ; j --){
        if(j >= w[i]){
            // 拿或者不拿
            dp[i][j] = dp[i-1][j] + dp[i-1][j-w[i]];
        }else{
            dp[i][j] = dp[i-1][j];
        }
    }
}
cout<<dp[n][m];

一维

for(int i = 0 ; i <= m ; i ++){
    dp[i] = 1;
}		
for(int i = 1 ; i <= n ; i ++){
    for(int j = m ; j >= 0 ; j --){
        if(j >= w[i]){
            dp[j] = dp[j] + dp[j-w[i]];
        }else{
            dp[j] = dp[j];
        }
    }
}
cout<<dp[m];

2：给n个物品，每个物品的体积为v，且只能选一次，求总体积恰好是m的方案数

//与1唯一的区别在初始化
//只有递归会到dp[0]这个状态才被计入方案数，所以只有dp[0] = 1
dp[0] = 1;
for(int i = 1 ; i <= n ; i ++){
    for(int j = m ; j >= 0 ; j --){
        if(j >= w[i]){
            dp[j] = dp[j] + dp[j-w[i]];
        }else{
            dp[j] = dp[j];
        }
    }
}
cout<<dp[m];

3：给n个物品，每个物品的体积为v，且只能选一次，求总体积至少是m的方案数

//初始化和2相同
dp[0] = 1;
for(int i = 1 ; i <= n ; i ++){
    for(int j = m ; j >= 0 ; j --){
        // 即使 j-w[i] < 0，也继续叠加方案数量。
        // 因为这个操作增多的方案数 == 大于m的方案数
        dp[j] = dp[j] + dp[max(0, j-w[i])];
    }
}
cout<<dp[m];

完全背包

模板题：蓝桥杯省赛无忧班（C&C++ 组）第 1 期 - 小明的背包2 - 蓝桥云课 (lanqiao.cn)

完全背包和01背包的区别是：完全背包中，每个物品都可以取无限次；而01背包，每个物品只能取1次。

一维数组的模板的变化很小，只需要修改遍历的方向（状态转移时考虑多次取当前物品）。

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

多重背包

多重背包和01背包的区别是：多重背包中，每个物品可以取s个，这个s是题目给定的；而01背包，每个物品只能取1次。

朴素O(N*S*M)

模板题：蓝桥杯省赛无忧班（C&C++ 组）第 1 期 - 小明的背包3 - 蓝桥云课 (lanqiao.cn)

多重背包可以一般退化为01背包来解决。

for(int i = 1 ; i <= n ; i ++){
    // 区别是每个物品需要跑si次, 就相当于有si个该物品
    while(s[i]--){
        for(int j = m ; j >= w[i] ; j --){
            dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
        }
    }
}
cout<<dp[m];

二进制优化O(N*logS*M)

模板题：蓝桥杯省赛无忧班（C&C++ 组）第 1 期 - 新一的宝藏搜寻加强版 - 蓝桥云课 (lanqiao.cn)

在进行二进制优化之前，我们首先要知道：

对于任意一个正整数n，都可以用二进制将其分解为：2^0 + 2^1 ... 2^m + 余数的形式。

任何小于n的正整数[1, n]，都可以取一其中的几个进行表示。

例如，10可以分解为1 + 2 + 4 + 3（这里的3是余数），然后[1, 10]的任意一个数都可以用这4个数表示，

有 3 == 1 + 2；6 == 1 +2 + 3；7 == 1 + 2 + 4

因此，我们对于s个物品，我们也可以用二进制的方式对它进行分解，以优化时间。

for(int i = 1 ; i <= n ; i ++){
    #if infIsTrue
    //若s[i] == 0时表示无限个，需要结合多重背包
     if(s[i] == 0){
         for(int j = w[i] ; j <= m ; j ++){
             dp[j] = max(dp[j], dp[j-w[i]] + v[i]);
         }
         continue;
     }    
    #endif
    // 常规
    // k从1开始，逐次加倍
    for(int k = 1 ; s[i] >= k ; s[i] -= k, k += k){
        for(int j = m ; j >= k*w[i] ; j --){
            dp[j] = max(dp[j], dp[j - k*w[i]] + k*v[i]);
        }
    }
    // 处理余数
    for(int j = m ; j >= s[i]*w[i] ; j --){
        dp[j] = max(dp[j], dp[j - s[i]*w[i]] + s[i]*v[i]);
    }
}
cout<<dp[m];

单调队列优化O(N*M)

模板题：6. 多重背包问题 III - AcWing题库

要使用单调队列对状态转移进行优化，我们首先要知道什么是单调队列 - OI Wiki。

此外，还有必要了解一种典型例题：154. 滑动窗口 - AcWing题库

下面提供，单调队列求滑动窗口最值的两种模板：

C++ STL

for(int i = 1 ; i <= n ; i ++){
    // 求最大值：dq.back() < a[i]
    while(dq.size() && dq.back() > a[i]){
        dq.pop_back();
    }
    dq.push_back(a[i]);
    if(i-k > 0 && dq.front() == a[i-k]) dq.pop_front();
    if(i-k >= 0) cout<<dq.front()<<" ";
}

非STL

hh = 0; tt = -1;
for(int i = 1 ; i <= n ; i ++){
    while(tt >= hh && a[q[tt]] > a[i]) tt--;
    q[++tt] = i;
    if(i-q[hh]+1 > k) hh++;
    if(i >= k) cout<<a[q[hh]]<<" ";
}

下面给出单调队列求解多重背包代码（AcWing 6. 多重背包问题 III【单调队列优化+图示】 - AcWing）

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1050;
const int maxm = 20050;

int n,m,tt,hh;
int w[maxn],v[maxn],s[maxn],q[maxm]; //这里q[maxm],而不是q[maxn]
int dp[maxn][maxm];

int main(void){
	cin>>n>>m;
	for(int i = 1 ; i <= n ; i ++){
		cin>>w[i]>>v[i]>>s[i];
	}
	for(int i = 1 ; i <= n ; i ++){
		for(int r = 0 ; r < w[i] ; r ++){
			hh = 0;tt = -1;
			for(int j = r ; j <= m ; j += w[i]){
				while(hh <= tt && j - q[hh] > s[i]*w[i]) hh++;
				while(hh <= tt && dp[i-1][q[tt]] + (j-q[tt])/w[i]*v[i] < dp[i-1][j]) tt--;
				q[++tt] = j;
				dp[i][j] = dp[i-1][q[hh]] + (j-q[hh])/w[i]*v[i];
			}
		}
	}
	cout<<dp[n][m];
	return 0;
}

二维费用背包

模板题：蓝桥杯省赛无忧班（C&C++ 组）第 1 期 - 小蓝的神秘行囊 - 蓝桥云课 (lanqiao.cn)

给n个物品，并给出每个物品的体积v，重量w和价值p，背包体积不超过V，重量不超过m，求能获得的最大价值。

只需要在01背包的基础上增加一个维度即可

for(int i = 1 ; i <= n ; i ++){
    for(int j = m ; j >= w[i] ; j --){
        for(int t = V ; t >= v[i] ; t --){
            dp[j][t] = max(dp[j][t], dp[j - w[i]][t - v[i]] + p[i]);
        }
    }
}

分组背包

给n组物品，每组物品有s个，给出每个物品的重量w和价值p，每组物品只能取其中一个，背包重量不超过m，求能获得的最大价值。

注意：同一组（i）的内不同物品的状态只能从上一组（i-1）转移过来。

二维DP写法：

分组编号i（分组内编号t（背包体积j）） -> 使用编号 i 和 i-1 避免了组内转移

for(int i = 1 ; i <= n ; i ++){
    for(int j = 0 ; j <= m ; j ++) dp[i][j] = dp[i-1][j];
    for(int t = 1 ; t <= cnt[i] ; t ++){
        for(int j = m ; j >= w[i][t] ; j --){
            dp[i][j] = max(dp[i][j], dp[i-1][j - w[i][t]] + v[i][t]);
        }
    }
}
cout<<dp[n][m];

一维DP写法：

分组编号i（背包体积j（分组内编号t）） -> 先遍历背包体积j，同样可以避免组内转移，且空间更优

for(int i = 1 ; i <= n ; i ++){
	for(int j = m ; j >= 0 ; j --){
        for(int t = 1 ; t <= cnt[i] ; t ++){
            if(j >= w[i][t]){
                dp[j] = max(dp[j], dp[j - w[i][t]] + v[i][t]);
            }
        }
    }
}