acwing算法基础课——背包问题笔记

大家好，欢迎来到IT知识分享网。

背包问题：

1. 01背包问题（每件物品只使用一次）
2. 完全背包问题（每件物品可以重复使用）
3. 多重背包问题
4. 分组背包问题 （物品有n组，每组物品有若干种，一组物品中只能选一种）

前言

本来是打算按照acwing算法基础课的顺序学的，但是对背包问题比较感兴趣，就想先把背包问题给学完。

一、01背包问题

1.1 题目描述

1.2 问题分析

背包问题如何表示当前状态？

f(i,j): 表示在选择i件物品的情况下，体积不大于j的最大价值。

划分情况

f(i,j)可以选择两种情况： 一种是选择第i件物品，一种是不选择第i件物品。

进行状态计算——集合划分（集合应该如何划分）

不含i就是相当于从前1~i-1个物品当中选，那么左边的集合状态就可以表示为f(i-1,j)。

含i就是从1~i个物品当中选，
从1~i个物品中选，还要包含第i个物品，那么f(i,j)相当于是前i-1个物品的最大价值加上第i个物品的价值

而 前i-1个物品的最大价值是f(i-1,j-v[i])

那么左右集合结果都出来了，那么该f(i,j)集合最大值应该如何表示？

1.3 状态表达式

易得 f(i,j) = max(f(i-1,j),f(i-1,j-v[i])+w[i])

1.4 朴素代码（二维）：

#include<iostream> using namespace std; const int N = 1010; int n,m; int v[N],w[N]; int f[N][N]; int main() { 
       cin>>n>>m; for(int i= 1;i<=n;i++) cin>>v[i]>>w[i]; //f[0][0~m] = 0,可以不写，默认为0 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]) 说明当前背包容量不能放下第i件物品 if(j>=v[i]) f[i][j] = max(f[i-1][j],f[i-1][j-v[i]]+w[i]); } } cout<<f[n][m]; } 

1.5 优化代码（一维）

#include<iostream> using namespace std; const int N = 1010; int n,m; int v[N],w[N];//v代表体积，w代表价值 int f[N]; 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 = m;j>=v[i];j--) //if(j从0到v[i]是无法进入判断的，所以可以优化循环里的j从v[i]开始) { 
       f[j] = max(f[j],f[j-v[i]]+w[i]); //而直接删除f[i]一行不可取 //因为删除后：f[j] = max(f[j],f[j-v[i]]+w[i]); //而正确的状态转移方程是：f[i][j] = max(f[i][j],f[i-1][j-v[i]]+w[i]); //删除后就相当于是 f[i][j] = max(f[i][j],f[i][j-v[i]]+w[i]),与原方程不等价 } } cout<<f[m]; } 

关键代码：

 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]; 

二、完全背包问题

2.1 问题描述

2.2问题分析

2.3朴素代码

#include<iostream> using namespace std; const int N = 1010; int f[N][N]; int n,m; int v[N],w[N]; 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++) { 
       for(int k = 0;k*v[i]<=j;k++) { 
       f[i][j] = max(f[i][j],f[i-1][j-k*v[i]]+w[i]*k); } } } cout<<f[n][m]; } 

2.4优化思路！

我们发现： f[i][j] = max(f[i-1][j],f[i-1][j-v]+w,f[i-1][j-2v]+2w,f[i-1][j-3v]+3w....) （1）式 f[i][j-v]=max(f[i-1][j-v],f[i-1][j-2v]+w,f[i-1][j-3v]+2w,f[i-1][j-4v]+3w..) (2) 式 是不是很像等差数列？？ 则我们易有 f[i][j-v]+w = max(f[i-1][j-v]+w,f[i-1][j-2v]+2w,f[i-1][j-3v]+3w,f[i-1][j-4v]+4w..) 则f[i][j] = max(f[i-1][j],f[i][j-v]+w) 则可以写出以下优化代码： 

2.4.1 优化代码（O(n^2))

#include<iostream> using namespace std; const int N = 1010; int n,m; int v[N],w[N]; int f[N][N]; 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][j-v[i]]+w[i]); } } cout<<f[n][m]; } 

2.4.2 再优化~

类比01背包问题的优化，上述代码还可以再优化

#include<iostream> using namespace std; const int N = 1010; int n,m; int v[N],w[N]; int f[N]; 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 = v[i];j<=m;j++) { 
       if(j>=v[i]) f[j] = max(f[j],f[j-v[i]]+w[i]); } } cout<<f[m]; } 

观察01背包问题和完全背包问题的代码：

//01背包问题 #include<iostream> using namespace std; const int N = 1010; int n,m; int v[N],w[N];//v代表体积，w代表价值 int f[N]; 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 = m;j>=v[i];j--) { 
       f[j] = max(f[j],f[j-v[i]]+w[i]); } } cout<<f[m]; } //完全背包问题 #include<iostream> using namespace std; const int N = 1010; int n,m; int v[N],w[N]; int f[N]; 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 = v[i];j<=m;j++) { 
       f[j] = max(f[j],f[j-v[i]]+w[i]); } } cout<<f[m]; } 

三.多重背包问题

3.1 题目描述

有 N 种物品和一个容量是 V 的背包。 第 i 种物品最多有 si 件，每件体积是 vi，价值是 wi。 求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。 输出最大价值。 输入格式 第一行两个整数，N，V，用空格隔开，分别表示物品种数和背包容积。 接下来有 N 行，每行三个整数 vi,wi,si，用空格隔开，分别表示第 i 种物品的体积、价值和数量。 输出格式 输出一个整数，表示最大价值。 数据范围 0<N,V≤100 0<vi,wi,si≤100 输入样例 4 5 1 2 3 2 4 1 3 4 3 4 5 2 输出样例： 10 

3.2 暴力写法（O(n^3))

#include<iostream> using namespace std; const int N = 110; int f[N]; int v[N],w[N],s[N]; int m,n; 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 = m;j>=v[i];j--) { 
       for(int k = 1;k*v[i]<=j&&k<=s[i];k++) { 
       f[j] = max(f[j],f[j-k*v[i]]+k*w[i]); } } } cout<<f[m]; } 

3.3 优化版本！

//不能像下面这样优化完全背包问题一样来优化多重背包问题。 f[i,j] = max(f[i-1,j],f[i-1,j-v]+w,f[i-1,j-2v]+2w,..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) 

优化方法：

我们可以从上面十组中凑出1024个物品。 1:0~1
2:0~3
4:0~7
8:0~15

//二进制优化 #include<iostream> #include<algorithm> using namespace std; const int N = 12010; int v[N],w[N],s[N]; int f[N]; int n,m;//表示物品种类和背包容积 int main() { 
       cin>>n>>m; int cnt = 0; for(int i = 1;i<=n;i++) { 
       int a,b,s; cin>>a>>b>>s; int k = 1; 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; //n表示转化为二进制后背包的大小 //开始01背包问题优化 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]; } 

四.分组背包问题

4.1 问题描述

有 N 组物品和一个容量是 V 的背包。 每组物品有若干个，同一组内的物品最多只能选一个。 每件物品的体积是 vij，价值是 wij，其中 i 是组号，j 是组内编号。 求解将哪些物品装入背包，可使物品总体积不超过背包容量，且总价值最大。 输出最大价值。 输入格式 第一行有两个整数 N，V，用空格隔开，分别表示物品组数和背包容量。 接下来有 N 组数据： 每组数据第一行有一个整数 Si，表示第 i 个物品组的物品数量； 每组数据接下来有 Si 行，每行有两个整数 vij,wij，用空格隔开，分别表示第 i 个物品组的第 j 个物品的体积和价值； 输出格式 输出一个整数，表示最大价值。 数据范围 0<N,V≤100 0<Si≤100 0<vij,wij≤100 输入样例 3 5 2 1 2 2 4 1 3 4 1 4 5 

4.2 AC代码

#include<iostream> #include<algorithm> using namespace std; const int N = 110; int n,m; int v[N][N],w[N][N],s[N]; int f[N]; int main() { 
       cin>>n>>m; for(int i = 1;i<=n;i++) { 
       cin>>s[i]; for(int j =0;j<s[i];j++) { 
       cin>>v[i][j]>>w[i][j]; } } for(int i= 1;i<=n;i++) { 
       for(int j= m;j>=0;j--) { 
       for(int k = 0;k<s[i];k++) { 
       if(v[i][k]<=j) f[j] = max(f[j],f[j-v[i][k]]+w[i][k]); } } } cout<<f[m]<<endl; }