layout: post
title: 背包入门
categories: [背包, 模板题]
description: 背包入门
keywords: 背包, 模板
背包
01背包
给定$N$个物品和容量是$V$的背包，以及N个物体的$v_i$和$w_i$，每个物体只有一件。
挑选一些物体，使得总体积小于等于V，目标是使得总价值最大，问最大价值是多少？
模板：01背包
朴素写法
//#define judge
// Author: oceanlvr
#include <bits/stdc++.h>
using namespace std;
int n, V;
const int maxn = 1e3 + 10;
int v[maxn];
int w[maxn];
int f[maxn][maxn];
int main() {
cin >> n >> V;
for (int i = 1; i <= n; i++) {
cin >> v[i] >> w[i];
}
for (int i = 1; i <= n; i++) {
for (int j = V; j <= 0; j--) {
f[i][j] = f[i - 1][j];
if (j >= v[i]) f[i][j] = max(f[i - 1][j], f[i - 1][j - v[i]] + w[i]);
}
}
cout << f[n][V];
return 0;
}
滚动数组优化空间
#define judge
// Author: oceanlvr
#include <bits/stdc++.h>
using namespace std;
int n, V;
const int maxn = 1e3 + 10;
int v[maxn];
int w[maxn];
int f[maxn];
int main() {
cin >> n >> V;
for (int i = 1; i <= n; i++) {
cin >> v[i] >> w[i];
}
/*
for (int i = 1; i <= n; i++) {
for (int j = V; j <= 0; j--) {
f[i][j] = f[i - 1][j];
if (j >= v[i]) f[i][j] = max(f[i - 1][j], f[i - 1][j - v[i]] + w[i]);
}
}
*/
for (int i = 1; i <= n; i++)
for (int j = V; j >= v[i]; j--) f[j] = max(f[j], f[j - v[i]] + w[i]);
cout << f[V];
return 0;
}
完全背包
给定$N$个物品和容量是$V$的背包，以及N个物体的$v_i$和$w_i$。每个物体有无限多件。
挑选一些物体，使得总体积小于等于$V$，目标是使得总价值最大，问最大价值是多少？
朴素写法
暴力做法：
for (int i = 1; i <= n; i++)
for (int j = V; j >= 0; j--) {
f[i][j] = f[i - 1][j];
for (int k = 0; k * v[i] <= j; k++)
f[i][j] = max(f[i][j], f[i - 1][j - v[i] * k] + w[i] * k);
}
时间优化
在枚举$k$时做时间优化：
因为在对k进行枚举时有：
$f[i][j]=max(f[i-1][j],f[i-1][j-v]+w,f[i-1][j-2v]+2w,…,f[i-1][j-kv]+kw)$
$\text{1:}f[i][j]=max(f[i-1][j],f[i-1][j-v]+w,f[i-1][j-2v]+2w,…,f[i-1][j-kv]+kw)$
$\text{2:}f[i][j-v]=max( f[i-1][j-v],f[i-1][j-2v]+w,f[i-1][j-kv]+(k-1)w)$
式子2中每一项都和式子1中从第二项开始的每一项相差1个w,那么就有:
完全背包的方程被优化为：$f[i][j] = max(f[i][j-v]+w,f[i-1][j])$
尤其注意以下细节：
for (int i = 1; i <= n; i++)
for (int j = 0; j <=V; j++){//正确
// for(int j=V;j>= v[i];j--){//错误
//错误的写法，因为f[i][j-v]在f[i][j]前面
//因此必须等f[i][j-v]更新之后才能更新f[i][j]
f[i][j]=f[i-1][j];
if(j>=v[i]) f[i][j]=max(f[i][j-v[i]]+w[i],f[i][j]);
}
#define judge
// Author: oceanlvr
#include <bits/stdc++.h>
using namespace std;
int n, V;
const int maxn = 1e3 + 10;
int w[maxn], v[maxn];
int f[maxn][maxn];
int main() {
cin >> n >> V;
for (int i = 1; i <= n; i++) {
cin >> v[i] >> w[i];
}
//------------------------------------------------------------------------------------
/*时间优化->优化枚举k,因为
1. f[i][j] =max(f[i-1][j],f[i-1][j-v]+w,f[i-1][j-2*v]+2*w,...,f[i-1][j-k*v]+k*w);
2. f[i][j-v] =max( f[i-1][j-v], f[i-1][j-2*v]+*w,...,f[i-1][j-k*v]+(k-1)*w);
综合1和2 f[i][j]=max(f[i-1][j],f[i][j-v]+w); 其中v是v_i，w是w_i
*/
for (int i = 1; i <= n; i++)
for (int j = 0; j <=V; j++){
// for(int j=V;j>= v[i];j--){
//错误的写法，因为f[i][j-v]在f[i][j]前面
//因此必须等f[i][j-v]更新之后才能更新f[i][j]
f[i][j]=f[i-1][j];
if(j>=v[i]) f[i][j]=max(f[i][j-v[i]]+w[i],f[i][j]);
}
//滚动数组优化
cout << f[n][V];
return 0;
}
空间优化
对于上述的方程：$f[i][j] = max(f[i][j-v]+w,f[i-1][j])$
观察方程$f[i][j]$可能是由$f[i][j-v[i]]$转移过来，并且之前的状态一定是在上一行的前面位置。
因此，可以得知$j-v$一定是在前面的数字情况，因此优化为1维的时候，前面的情况一定是上一个维度的。
优化空间的步骤,将阶段那一维度删除：即将i删除。
随后对
代码如下：
for (int i = 1; i <= n; i++)
for (int j = v[i]; j <=V; j++){
f[j]=max(f[j-v[i]]+w[i],f[j]);
}
整合：
// Author: oceanlvr
#include <bits/stdc++.h>
int n, V;
const int maxn = 1e3 + 10;
int w[maxn], v[maxn];
// int f[maxn][maxn];
int f[maxn];
int main() {
cin >> n >> V;
for (int i = 1; i <= n; i++) {
cin >> v[i] >> w[i];
}
//朴素的完全背包
/*
for (int i = 1; i <= n; i++)
for (int j = V; j >= 0; j--) {
f[i][j] = f[i - 1][j];
for (int k = 0; k * v[i] <= j; k++)
f[i][j] = max(f[i][j], f[i - 1][j - v[i] * k] + w[i] * k);
}
*/
//------------------------------------------------------------------------------------
/*时间优化->优化枚举k,因为
1. f[i][j] =max(f[i-1][j],f[i-1][j-v]+w,f[i-1][j-2*v]+2*w,...,f[i-1][j-k*v]+k*w);
2. f[i][j-v] =max( f[i-1][j-v], f[i-1][j-2*v]+*w,...,f[i-1][j-k*v]+(k-1)*w);
综合1和2 f[i][j]=max(f[i-1][j],f[i][j-v]+w); 其中v是v_i，w是w_i
*/
/*
for (int i = 1; i <= n; i++)
for (int j = 0; j <=V; j++){
// for(int j=V;j>= v[i];j--){
//错误的写法，因为f[i][j-v]在f[i][j]前面
//因此必须等f[i][j-v]更新之后才能更新f[i][j]
f[i][j]=f[i-1][j];
if(j>=v[i]) f[i][j]=max(f[i][j-v[i]]+w[i],f[i][j]);
}
*/
//滚动数组优化
for (int i = 1; i <= n; i++)
for (int j = v[i]; j <=V; j++){
f[j]=max(f[j-v[i]]+w[i],f[j]);
}
// cout << f[n][V];
cout << f[V];
return 0;
}
多重背包
给定$N$个物品和容量是$V$的背包，以及N个物体的$v_i$和$w_i$。每个物体有$s_i$件。
挑选一些物体，使得总体积小于等于V，目标是使得总价值最大，问最大价值是多少？
朴素写法
暴力做法$O(n^2)$
#define judge
// Author: oceanlvr
#include <bits/stdc++.h>
using namespace std;
int n, V;
const int maxn = 1e2 + 10;
int s[maxn], v[maxn], w[maxn];
int f[maxn][maxn];
int main() {
#ifndef judge
freopen("E:/yxc/in.txt", "r", stdin);
freopen("E:/yxc/out.txt", "w", stdout);
#endif
cin >> n >> V;
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 <= V; j++) {
f[i][j] = f[i - 1][j];
for (int k = 0; k <= s[i]; k++) {
if (j >= k * v[i]) {
f[i][j] = max(f[i][j], f[i - 1][j - k * v[i]] + k * w[i]);
}
}
}
}
cout << f[n][V] << endl;
return 0;
}
优化时间
时间优化：
思路1：单调队列优化多重背包 背包问题 (附单调队列优化多重背包)
思路2：倍增的思想，把多重背包转为01背包，使用二进制对$s[i]$里面的数字范围打包：
用倍增的思想对同一物体进行打包之后物体的数目从$S$变为了$lgS$。因此时间复杂度由原来的$O(NSV)$变为$O(NV\text{lg}V)$。
建议看下『算法竞赛进阶指南』这本书上讲解倍增思想的部分。
//#define judge
// Author: oceanlvr
#include <bits/stdc++.h>
using namespace std;
int n, V;
const int maxn = 2e4 + 5e3 + 10;
const int maxm = 2e3 + 10;
int v[maxn], w[maxn];
int f[maxn];
int main() {
cin >> n >> V;
int cnt = 0; //打包后的物体的编号
for (int i = 1; i <= n; i++) {
int a, b, s;
cin >> a >> b >> s;
int k = 1;
/*倍增的思想多多重背包打包，转为01背包*/
while (k <= s) {
cnt++;
//将这k个物体打包成一个物体，编号为cnt
v[cnt] = a * k;
w[cnt] = b * k;
s -= k;
k <<= 1; //倍增
}
if (s) {
//此时还剩下没有够2^{k+1}个的单位
//单独补上为一个物体
cnt++;
v[cnt] = a * s;
w[cnt] = b * s;
}
}
n = cnt; //更新为01背包的大小
//打包之后的多重背包转化为01背包
//此时直接做01背包相同的操作即可
for (int i = 1; i <= n; i++) {
for (int j = V; j >= v[i]; j--) {
f[j] = max(f[j], f[j - v[i]] + w[i]);
}
}
cout << f[V] << endl;
return 0;
}
分组背包问题
将物品分为$N$组，每个组有若干个物体，给定若干物体的价值$w_i$。每组只能选一个物体（组内是互斥的）。
问有背包的价值最大是多少？
朴素写法
// Author: oceanlvr
#include <bits/stdc++.h>
using namespace std;
int n, V;
const int maxn = 1e2 + 10;
//第i组的第j个物品的体积和价值
int v[maxn][maxn];
int w[maxn][maxn];
int f[maxn][maxn];
int main() {
cin >> n >> V;
for (int i = 1; i <= n; i++) {
int nn;
cin >> nn;
v[i][0] = nn; //记录数量
for (int j = 1; j <= nn; j++) {
cin >> v[i][j] >> w[i][j];
}
}
//朴素写法
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= V; j++) {
for (int k = 0; k <= v[i][0]; k++) {
f[i][j] = max(f[i][j], f[i - 1][j]);
if (j - v[i][k] >= 0)
f[i][j] = max(f[i][j], f[i - 1][j - v[i][k]] + w[i][k]);
}
}
}
cout << f[n][V] << endl;
空间优化
滚动数组空间优化：
对于分组背包的空间优化意义不太大，因为本身存储$v$和$w$就已经是二维的空间花销了。
// Author: oceanlvr
#include <bits/stdc++.h>
using namespace std;
int n, V;
const int maxn = 1e2 + 10;
//第i组的第j个物品的体积和价值
int v[maxn][maxn];
int w[maxn][maxn];
int f[maxn];
int main() {
cin >> n >> V;
for (int i = 1; i <= n; i++) {
int nn;
cin >> nn;
v[i][0] = nn; //记录数量
for (int j = 1; j <= nn; j++) {
cin >> v[i][j] >> w[i][j];
}
}
//空间优化
for (int i = 1; i <= n; i++) {
for (int j = V; j >= 0; j--) {
for (int k = 0; k <= v[i][0]; k++) {
if (j - v[i][k] >= 0)
f[j] = max(f[j], f[j - v[i][k]] + w[i][k]);
}
}
}
cout << f[V] << endl;
综合
// Author: oceanlvr
#include <bits/stdc++.h>
using namespace std;
int n, V;
const int maxn = 1e2 + 10;
//第i组的第j个物品的体积和价值
int v[maxn][maxn];
int w[maxn][maxn];
// int f[maxn][maxn];
int f[maxn];
int main() {
cin >> n >> V;
for (int i = 1; i <= n; i++) {
int nn;
cin >> nn;
v[i][0] = nn; //记录数量
for (int j = 1; j <= nn; j++) {
cin >> v[i][j] >> w[i][j];
}
}
/*朴素写法
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= V; j++) {
for (int k = 0; k <= v[i][0]; k++) {
f[i][j] = max(f[i][j], f[i - 1][j]);
if (j - v[i][k] >= 0)
f[i][j] = max(f[i][j], f[i - 1][j - v[i][k]] + w[i][k]);
}
}
}
*/
//空间优化
for (int i = 1; i <= n; i++) {
for (int j = V; j >= 0; j--) {
for (int k = 0; k <= v[i][0]; k++) {
if (j - v[i][k] >= 0)
f[j] = max(f[j], f[j - v[i][k]] + w[i][k]);
}
}
}
cout << f[V] << endl;
return 0;
}
