B站上的一位大佬将的还挺不错可以点击观看
本片博客的例题来源都还挺不错的可以进去看看
背包问题对于学动态规划还是挺有帮助的，写的比较简单，对于01背包可以自己画个流程图多跑几遍就可以了！个人感悟比较错漏！
01背包
01背包九讲里面最简单的一种了，但是也是最重要的一种，其他的几种基本上都可以用01背包的解题思路来去解决，接下来结合例题来解决一下吧；
有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。
第 i 件物品的体积是 vi，价值是 wi。
求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
输出最大价值。
输入格式
第一行两个整数，N，V，用空格隔开，分别表示物品数量和背包容积。
接下来有 N 行，每行两个整数 vi,wi，用空格隔开，分别表示第 i 件物品的体积和价值。
输出格式
输出一个整数，表示最大价值。
数据范围
0<N,V≤1000
0<vi,wi≤1000
输入样例
4 5
1 2
2 4
3 4
4 5
输出样例：
8
这个题可以说是最直白的01背包了，我们可以用一个二维的滚动数组来存背包当前是否能装的下这件物品，然后从第一个到以后一个物品一个一个的便利，然后用数组的列表示当前背包容量为j的时候可以装的最大价值是多少；如果j小于当前的重量，那么就能装的下，他的容积就是上一个物品时的价值；说的不是很清楚直接看代码吧！
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1005;
int w[MAXN]; // 重量
int v[MAXN]; // 价值
int f[MAXN][MAXN]; // f[i][j], j重量下前i个物品的最大价值
int main()
{
int n, m;
cin >> n >> m;
for(int i = 1; i <= n; ++i)
cin >> w[i] >> v[i];
for(int i = 1; i <= n; ++i) //依次便利每个背包
for(int j = 1; j<=m; ++j)
{
// 当前重量装不进，价值等于前i-1个物品
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]]+v[i]);
}
return 0;
}
其是还可以对空间复杂度进行一波优化
#include <iostream>
using namespace std;
const int N=1010;
int v[N],w[N],dp[N]={0};
int main()
{
int n,V;
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;j--)
{
if(j>=v[i])dp[j]=max(dp[j-v[i]]+w[i],dp[j]);//这里改用了一维的；
}
cout << dp[V];
return 0;
}
完全背包
完全背包和01背包的不同之处就是完全背包的每个物品可以被无限次的拿，而01的只能被拿一次；
这里我们只说一个优化空间复杂度过的版本，直接看例题吧
有 N 种物品和一个容量是 V 的背包，每种物品都有无限件可用。
第 i 种物品的体积是 vi，价值是 wi。
求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
输出最大价值。
输入格式
第一行两个整数，N，V，用空格隔开，分别表示物品种数和背包容积。
接下来有 N 行，每行两个整数 vi,wi，用空格隔开，分别表示第 i 种物品的体积和价值。
输出格式
输出一个整数，表示最大价值。
数据范围
0<N,V≤1000
0<vi,wi≤1000
输入样例
4 5
1 2
2 4
3 4
4 5
输出样例：
10
01背包是是从大倒下一次遍历背包的容量，这是为了避免重复的那一个值，我我们可以从小到大一次遍历，加入背包的容量为5，第一个物品的价值为2体积为1；当j等一的时候我们遍历了一次，然后dp[1]=2；当j=2时dp[2]=max(dp[2],dp[2-1]+2);这样刚好有取了一遍是不是很巧？我们只要从开始一直遍历到最后就可以了；然后输出dp[V]就可以了；
#include <iostream>
#include <algorithm>
using namespace std;
const int N= 1010;
int n,m;
int dp[N];
int v[N];
int 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 = v[i];j <= m ;j++){
arr[j] = max(dp[j] , dp[j-v[i]]+w[i]);//每次保留最大的
}
}
cout <<dp[m];
return 0;
}
多重背包
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
这个是最最基础的多重背包了，我们只需要加上一个循环作为判断就行了
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1005;
int w[MAXN]; // 重量
int v[MAXN]; // 价值
int s[MAXN]; // 物品数量
int f[MAXN]; // f[i][j], j重量下前i个物品的最大价值
int main()
{
int n;
int m; // 背包重量
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 j = m; j>=0; --j)
for(int k = 1; k <= s[i]; ++k) //遍历拿几个的时候最大
if(j>=k*w[i])
f[j] = max(f[j], f[j-k*w[i]]+k*v[i]);
cout << f[m] << endl;
return 0;
}
2
1的时间复杂度是nmk的如果遇到数据比较就没办法了需要进行优化我们这次说的是二进制优化；
有 N 种物品和一个容量是 V 的背包。
第 i 种物品最多有 si 件，每件体积是 vi，价值是 wi。
求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。
输出最大价值。
输入格式
第一行两个整数，N，V，用空格隔开，分别表示物品种数和背包容积。
接下来有 N 行，每行三个整数 vi,wi,si，用空格隔开，分别表示第 i 种物品的体积、价值和数量。
输出格式
输出一个整数，表示最大价值。
数据范围
0<N≤1000
0<V≤2000
0<vi,wi,si≤2000
提示：
本题考查多重背包的二进制优化方法。
输入样例
4 5
1 2 3
2 4 1
3 4 3
4 5 2
输出样例：
10
这一题如果我们直接暴力搜索那么肯定会超时的，所以需要进行一些优化，emmm什么一次呢，第一种情况是从0到k每次去不同的数，那么我们能不能想办法将这个过程给优化一波呢？答案是可以的，例如7以内的数我们可以用1,2,4这三个数表示。3=1+2,5=1+4；6=2+4；7=1+2+4，因此我们可以用二进制的性质将k进行优化
#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
int n,m,v,w,s;
int dp[3000];
vector<int>ve;
int main()
{
cin>>n>>m;
for(int i=0;i<n;i++)
{
cin>>v>>w>>s;
ve.clear() ;
for(int q=1;q<s;q<<=1)//将 s 用 二进制的数表示 每次将 q 乘以2，保证是2的整数次方
{
s-=q;
ve.push_back(q);
}
if(s) ve.push_back(s); //如果最后s有剩余，就单独放入；
for(int k=0;k<ve.size();k++)
{
for(int j=m;j>=v*ve[k];j--)//遍历ve中的数据作为01背包，每个数据只会有取和不去的两种选项
{
dp[j]=max(dp[j],dp[j-ve[k]*v]+ve[k]*w);
}
}
}
cout<<dp[m]<<endl;
return 0;
}
3
emmm第三种还不是很会，用到的知识是单调队列！有兴趣的可以自己学习一下
混合背包
混合背包就是讲前面的几种情况混合起来了，我们计算的时候只用分类计算就行了，还是之前的问题
有 N 种物品和一个容量是 V 的背包。
物品一共有三类：
第一类物品只能用1次（01背包）；
第二类物品可以用无限次（完全背包）；
第三类物品最多只能用 si 次（多重背包）；
每种体积是 vi，价值是 wi。
求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。
输出最大价值。
输入格式
第一行两个整数，N，V，用空格隔开，分别表示物品种数和背包容积。
接下来有 N 行，每行三个整数 vi,wi,si，用空格隔开，分别表示第 i 种物品的体积、价值和数量。
si=−1 表示第 i 种物品只能用1次；
si=0 表示第 i 种物品可以用无限次；
si>0 表示第 i 种物品可以使用 si 次；
输出格式
输出一个整数，表示最大价值。
数据范围
0<N,V≤1000
0<vi,wi≤1000
−1≤si≤1000
输入样例
4 5
1 2 -1
2 4 1
3 4 0
4 5 2
输出样例：
8
这一题直接分类计算就行了
#include<iostream>
#include<algorithm>
#include<string.h>
#include<vector>
using namespace std;
int n,m,v,w,s;
int dp[3000];
vector<int>ve;
int main()
{
cin>>n>>m;
for(int i=0;i<n;i++)
{
cin>>w>>v>>s;
ve.clear() ;
if(s>0){ //如果是多重的用二进制进行优化
for(int p=1;p<s;p<<=1)
{
ve.push_back(p);
s=s-p;
}
if(s) ve.push_back(s);
}
if(!s)//完全背包
{
for(int j=w;j<=m;j++)
{
dp[j]=max(dp[j],dp[j-w]+v);
}
}
else if(s>0){//多重背包
for(int k=0;k<ve.size();k++)
{
for(int j=m;j>=w*ve[k];j--)
dp[j]=max(dp[j],dp[j-w*ve[k]]+ve[k]*v);
}
}
else{//01背包
for(int j=m;j>=w;j--)
{
dp[j]=max(dp[j],dp[j-w]+v);
}
}
}
cout<<dp[m]<<endl;
return 0;
}
二维费用的背包问题
其实二维费用背包也是很简单的就是将滚动数组多开一维用来分别存储体积和质量罢了！
有 N 件物品和一个容量是 V 的背包，背包能承受的最大重量是 M。
每件物品只能用一次。体积是 vi，重量是 mi，价值是 wi。
求解将哪些物品装入背包，可使物品总体积不超过背包容量，总重量不超过背包可承受的最大重量，且价值总和最大。
输出最大价值。
输入格式
第一行两个整数，N，V,M，用空格隔开，分别表示物品件数、背包容积和背包可承受的最大重量。
接下来有 N 行，每行三个整数 vi,mi,wi，用空格隔开，分别表示第 i 件物品的体积、重量和价值。
输出格式
输出一个整数，表示最大价值。
数据范围
0<N≤1000
0<V,M≤100
0<vi,mi≤100
0<wi≤1000
输入样例
4 5 6
1 2 3
2 4 4
3 4 5
4 5 6
输出样例：
8
#include<iostream>
#include<algorithm>
#include<string.h>
using namespace std;
int n,V,M;
int dp[1500][1500];
int v,m,w;
int main()
{
cin>>n>>V>>M;
for(int i=0;i<n;i++)
{
cin>>v>>w>>m;
for(int j=V;j>=v;j--)//两个循环分别遍历体积的质量遍历的规则和一维的一样
{
for(int k=M;k>=w;k--)
{
dp[j][k]=max(dp[j][k],dp[j-v][k-w]+m);
}
}
}
cout<<dp[V][M]<<endl;
return 0;
}
背包问题求方案数
这类问题我们只需要再开一个数组标记方案书就行了中间有点小细节注意一下
有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。
第 i 件物品的体积是 vi，价值是 wi。
求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
输出 最优选法的方案数。注意答案可能很大，请输出答案模 109+7 的结果。
输入格式
第一行两个整数，N，V，用空格隔开，分别表示物品数量和背包容积。
接下来有 N 行，每行两个整数 vi,wi，用空格隔开，分别表示第 i 件物品的体积和价值。
输出格式
输出一个整数，表示 方案数 模 109+7 的结果。
数据范围
0<N,V≤1000
0<vi,wi≤1000
输入样例
4 5
1 2
2 4
3 4
4 6
输出样例：
2
#include<string.h>
#include<iostream>
#include<algorithm>
using namespace std;
int dp[1090];
int flag[1090];
int n,v,V,m;
const int mod=1e9+7;
int main()
{
cin>>n>>V;
flag[0]=1;
for(int i=0;i<n;i++)
{
cin>>v>>m;
for(int j=V;j>=v;j--)
{
int s=0;
int t=max(dp[j],dp[j-v]+m);//还和之前的一样遍历只是中间需要记录路径数所以不能直接赋值
if(t==dp[j]) s+=flag[j];//当t=dp[j]时s加上flag【j】
if(t==dp[j-v]+m) s=s+flag[j-v];//当t=dp[j-v]+m时s加上flag[j-v]
flag[j]=s%mod;//注意取mod 只是因为 有可能两种不同的路径取出来的最大值是相同的
dp[j]=t;
}
}
int maxn=-1;
int sum=0;
for(int i=0;i<=V;i++) maxn=max(maxn,dp[i]);//遍历最大值
for(int i=0;i<=V;i++)
{
if(dp[i]==maxn)
{
sum=(sum+flag[i])%mod;//路径相加
}
}
cout<<sum<<endl;
return 0;
}
背包问题求具体方案
这个问题看上去和上一个很像但是区别还是不小的吧
有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。
第 i 件物品的体积是 vi，价值是 wi。
求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
输出 字典序最小的方案。这里的字典序是指：所选物品的编号所构成的序列。物品的编号范围是 1…N。
输入格式
第一行两个整数，N，V，用空格隔开，分别表示物品数量和背包容积。
接下来有 N 行，每行两个整数 vi,wi，用空格隔开，分别表示第 i 件物品的体积和价值。
输出格式
输出一行，包含若干个用空格隔开的整数，表示最优解中所选物品的编号序列，且该编号序列的字典序最小。
物品编号范围是 1…N。
数据范围
0<N,V≤1000
0<vi,wi≤1000
输入样例
4 5
1 2
2 4
3 4
4 6
输出样例：
1 4
用一个标记数组进行标记然后从大到小遍历，每次标记被取得，然后再从小到大进行查找
#include<iostream>
#include<algorithm>
#include<string.h>
using namespace std;
int n,v[1500],w[1500],m;
int f[1500],dp[1500][1500];
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>v[i]>>w[i];
for(int i=n;i>=1;i--)//因为需要标记所以用二维的数组进行储存
{
for(int j=0;j<=m;j++)
{
if(j<v[i]) dp[i][j]=dp[i+1][j];
else
dp[i][j]=max(dp[i+1][j],dp[i+1][j-v[i]]+w[i]);
}
}
for(int i=1;i<=n;i++)
{
if(m-v[i]>=0&&dp[i][m]==dp[i+1][m-v[i]]+w[i])//如果满足条件就进行输出
{
cout<<i<<" ";
m-=v[i];//进行查找下一个位置，这个节点连接的，可能有点难理解自己画个图模拟一遍就可以了
}
if(m==0) break;
}
return 0;
}
有依赖的背包问题
这个是真不会还用到了树形dp，分组背包，emmm以后再补吧
京公网安备 11010502036488号