投稿
  1. 首页
  2. C

第一DP：简单的背包模板

code • 2022-4-19 • C • 阅读 37

第一DP：简单的背包模板,第1张

DP之背包
  • 什么是 DP ？
  • 背包问题
    • 什么是背包问题
    • 01背包
    • 完全背包
    • 分组背包
      • 例1
      • 例2
    • 多重背包
      • 无优化
      • 空间优化
      • 二进制优化
      • 单调队列优化

什么是 DP ？
DP阵营图必须要有状态转移其实有转移就可以一定要有转移吗？
一定要求的最优化动态规划毫无疑问是DP搜索也可以是DP静态规划为什么不是DP？
不用最优也可以神经网络是DP二分也是DP蒙特卡洛当然也是DP
最优是什么？递归难道不是DP？映射也很DPDual Problem才是正统DP！

咳咳，这里的DP可不是Dual Problem，而是Dynamic Programming。


按解法分类，可以将动态规划以下几类：

  1. 暴力
  2. 暴力+优化
  3. 暴力+算法
  4. 暴力+算法+优化
  5. 挖坑待填
  6. 挖坑待填
    咳咳，简单来说就是，简单的选与不选，和困难的选与不选。

    当然，分类不重要，毕竟它是我主观的，在成体系前你看不懂就没用。

    所以，前四类就统称为暴力好了。


    当然，我认为背包问题不能算进分类里。

    它是板子，人人都应该会和背。

背包问题 什么是背包问题

有物品，有背包，有题目就是背包问题
咳咳。

题目会给出一个或多个限制，和一些供选取的东西，问怎么选东西最优之类的。


果然还是不懂吧，说了白说，直接看题。

01背包

体积V。

N种物品，各体积vi，价值wi，每种最多选1个。

问最大价值。

#include//acwing2
using namespace std;
int N,V,v[1010],w[1010],dp[1010];
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>=v[i]; j--) {
			dp[j]=max(dp[j],dp[j-v[i]]+w[i]);
		}
	}
	cout<<dp[V];
	return 0;
}

显然可分为装与不装，那么dp[i]表示体积为i时的最大价值。


那么暴力枚举每件物品i，对于能装下v[i]所有体积，在装与不装之间取最优：
for i:1->N
for j:v->V
dp[i]=max(self,dp[i-v]+w)
但是考虑后无效性，枚举体积时倒序：
for i:1->N
for j:V->v
dp[i]=max(self,dp[i-v]+w)

完全背包

体积V。

N种物品，体积vi，价值wi，可无限选。

问最大价值。

#include//acwing3
using namespace std;
int N,V,v[1010],w[1010],dp[1010];
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[i]; j<=V; j++) {//
			dp[j]=max(dp[j],dp[j-v[i]]+w[i]);
		}
	}
	cout<<dp[V];
	return 0;
}

显然，代码上相对01背包就变了个循环方向。


01背包需要确保后无效性，而完全背包需要确保后有效性。

分组背包

体积V。

N组物品，物品体积vij价值wij。

限制每组的选择策略。

问最大价值。

它规定了组内的某种选择规则，所以叫分组背包。

例1

总体积V，N组物品，每组最多选1个，物品体积vij价值wij。

问最大价值。

#include//acwing9
using namespace std;
int N,V,n[110],v[110][110],w[110][110];
int f[110][10010];
int main() {
	cin>>N>>V;
	for(int i=1; i<=N; i++) {
		cin>>n[i];
		for(int j=1; j<=n[i]; j++) {
			cin>>v[i][j]>>w[i][j];
		}
	}
	for(int i=1; i<=N; i++) {//枚举组
		for(int k=1; k<=V; k++) {//对于所有体积
			f[i][k]=f[i-1][k];//不选
			for(int j=1; j<=n[i]; j++) {//选哪个
				if(k>=v[i][j]) {//能不能选
					f[i][k]=max(f[i][k],f[i-1][k-v[i][j]]+w[i][j]);//能不能更新
				}
			}
		}
	}
	cout<<f[N][V];
	return 0;
}

f[i][k]第i组 体积为k时 的最大价值
k_max=100组*100=10000
一组一组的处理，处理出所有体积的最大价值f。


f[i][k]=max(self, f[i-1][k-v[i][j]] + w[i][j]);
更新当前f[i]，用的都是上一组的f[i-1]，保证了后无效性。

例2

体积V。

N种物品，体积1，价值由选取数量决定，为wij。

问最大价值。

#includencstoj1760
#define ll long long
using namespace std;
ll n,m,ans,a[550][550],f[550][550];
int main() {
	cin>>n>>m;//n种物品，背包体积m
	for(int i=1; i<=n; i++) {//枚举组
		for(int j=1; j<=m; j++) {//选j个时的wij
			cin>>a[i][j];
		}
	}
	for(int i=1; i<=n; i++) {//枚举组
		for(int k=1; k<=m; k++) {//枚举当前占用的背包体积，因为wij>0，所以k可以从1开始
			for(int j=0; j<=m; j++) {//跟选j个比较，先处理j=0，也就是不选
				if(k>=j) f[i][k]=max(f[i][k],f[i-1][k-j]+a[i][j]);
			}
		}
	}
	cout<<f[n][m];
	return 0;
}

熟练了应该知道，k的循环和j的循环 顺序可以交换。


咳咳。

其实这根本无关紧要。


先从三维来看：

#include
#define ll long long
using namespace std;
ll n,m,ans,a[550][550],f[550][550][550];
int main() {
	cin>>n>>m;
	for(int i=1; i<=n; i++) {
		for(int j=1; j<=m; j++) {
			cin>>a[i][j];
		}
	}
	for(int i=1; i<=n; i++) {
		for(int j=1; j<=m; j++) {
			f[i][j][j]=a[i][j];//预处理
		}
	}
	for(int k=1; k<=m; k++) {
		for(int i=1; i<=n; i++) {
			for(int j=1; j<=m; j++) {
				f[i][j][k]=max(f[i][j][k],f[i][j-1][k-1]-a[i][j-1]+a[i][j]);//选
				f[i+1][0][k]=max(f[i+1][0][k],f[i][j-1][k]);//不选
			}
		}
	}
	for(int k=1; k<=m; k++) {
		for(int i=1; i<=n; i++) {
			for(int j=1; j<=m; j++) {
				ans=max(ans,f[i][j][k]);
			}
		}
	}
	cout<<ans;
	return 0;
}

三维显然爆空间，所以写起来也不用在意一些细节反正是错的 。


考虑从小到大遍历体积，也就是选了k个，那么对于(i,j)：
选, f[i][j][k]=max(self,f[i][j-1][k-1]-a[i][j-1]+a[i][j])
不选, f[i+1][0][k]=max(self,f[i][j][k])
明显需要预处理，f[i][j][j]=a[i][j]。

明显有问题反正是错的。

显然对于(i,j)，即使k=1也会更新f[i][j][k]，大量内存浪费，可以去掉一维。


首先想到因为每次只处理一排，所以去掉[i]。

但是由于思路是不思考细节，直接存储所有(i,j)再取最大。

而去掉[i]之后无法预处理后续数据，pass。


再考虑去掉[j]，因为m=V，所以f[i][k]完全可以存下。


降维后再考虑细节，首先是状态转移式：
f[i][k]=max(f[i][k],f[i-1][k-j]-a[i][j-1]+a[i][j]);
因为没有j，所以必须用j更新，-1改-j。


改成-j后要在前面加pd，还要考虑后无效性，所以i改i-1，直接用上一排，也不用额外存了。


再是dp前的预处理，直接存就行，所以直接变。

当然，思考一下就会发现，可以省略。


再是循环，因为降维后处理这一排变成-j，必须保证遍历过的排的结果都是对的。


所以遍历k要放i里面，至于j里j外就没有限制了。

因为要变成-j，所以j要从0开始。


最后是结果，f[n][m]。

这就是个混沌的降维过程了。


小结：
三个老问题，怎么选，怎么不选，考虑后效性
1.直接继承就是不选
2.更新最优价值就是选
3.倒序遍历或者避开正在和将要处理的那组数据可以消除后效性
细节，循环顺序（含义），是否预处理（过程）

多重背包

体积V。

N种物品，体积Vi价值Wi，每种最多选Si个。

问最大价值。

无优化 
#include//acwing4
using namespace std;
int N,V,k,v[10010],w[10010],dp[10010];
int main() {
	cin>>N>>V;
	for(int i=1; i<=N; i++) {
		int a,b,c;
		cin>>a>>b>>c;
		for(int i=1; i<=c; i++) {
			v[++k]=a;
			w[k]=b;
		}
	}
	for(int i=1; i<=k; i++) {
		for(int j=V; j>=v[i]; j--) {
			dp[j]=max(dp[j],dp[j-v[i]]+w[i]);
		}
	}
	cout<<dp[V];
	return 0;
}

一种有Si个的物品，拆成Si种只有一个的物品，变成01背包

空间优化 
#include//acwing4
using namespace std;
int N,V,v,w,s,dp[1005];
int main() {
	cin>>N>>V;
	while(N--) {
		cin>>v>>w>>s;
		for(int i=1; i<=s; i++)
			for(int j=V; j>=v; j--)
				dp[j]=max(dp[j],dp[j-v]+w);
	}
	cout<<dp[V];
}

降低代码量，同时节省空间

二进制优化 
#include//acwing5
using namespace std;
int N,V,k,v[200010],w[200010],dp[200010];
int main() {
	cin>>N>>V;
	for(int i=1; i<=N; i++) {
		int a,b,c;
		cin>>a>>b>>c;
		for(int g=1; g<=c; g*=2) {
			c-=g;
			v[++k]=a*g;
			w[k]=b*g;
		}
		if(c>0) {
			v[++k]=a*c;//
			w[k]=b*c;
		}
	}
	for(int i=1; i<=k; i++) {
//		cout<
	}
	for(int i=1; i<=k; i++) {
		for(int j=V; j>=v[i]; j--) {
			dp[j]=max(dp[j],dp[j-v[i]]+w[i]);
		}
	}
	cout<<dp[V];
	return 0;
}

每次多拆一些，拆下2^k个变成1种物品。

单调队列优化 
#include//acwing6
using namespace std;
int dp[20010],pre[20010],q[20010];//q存当前窗口内数字的下标, 也就是当前体积k 
int n,m;
int main() {
    cin>>n>>m;
    for(int i=0; i<n; i++) {
        memcpy(pre,dp,sizeof dp);//要用单调队列导致不能倒序循环, 记忆化 
        int v,w,s;
        cin>>v>>w>>s;
        for(int j=0; j<v; j++) {//枚举余数, 因为每个余数可以单独考虑 
        	//每个余数下, 都只用考虑从V-0到V-n*v[i]转移来的状态, 其中均加的加数不用管 
            int head=0,tail=-1;
            for(int k=j; k<=m; k+=v) {//单调队列, 共O(n), 求出选0个到选满的最优解 
                if(head<=tail && k-s*v>q[head]) head++;
                while(head<=tail && pre[q[tail]]-(q[tail]-j)/v*w<=pre[k]-(k-j)/v*w) tail--;
                q[++tail]=k;
				if(head<=tail) dp[k]=max(dp[k], pre[q[head]]+(k-q[head])/v*w);
            }
        }
    }
    cout<<dp[m];
    return 0;
}
/*
学习前置要求: 空间优化的多包1, 滑动窗口 
多包1中每件物品的v, 用j%v分成独立的v组, 每组内用单调队列求最大 
滑动窗口求的是定长窗口内最大, 及时输出. 本题求当前%v的余数下, 待求队列（选1个到选满）中的最大值 
k是当前余数加上选了n个的体积, 枚举k便枚举了当前余数的所有体积情况, 是待求队列 
不同的是, 本题中该队列有后效性, 算一次, 整个队列就均加一个数, 但不影响求最大值 
然后窗口大小根据k-s*v变化 
具体的,  
选-1个是head>tail, 选s+1个是k-s*v<=q[head] , 即头下标体积大等于当前体积-选了s个 
算了, 模拟一下, 最开始单调队列无元素, 默认待求队列单调 
进第一个元素: 
	head>tail, 数字不够不能动头
	head>tail, 数字不够不能删尾
	进第一个元素 
	head<=tail, 更新当前体积最优解
进第二个元素: (若单调且当前体积不够)
	head<=tail, q[head]>=k-s*v, 头体积大于当前体积-全装进去体积, 
	# 而如果当前体积-全装进去体积更大, 就是已经全装进去了, 但是现在还有k没处理完, 前面的必须扔掉了 
	head<=tail, pre[q[tail]]-(q[tail]-j)/v*w<=pre[k]-(k-j)/v*w, 上一个最大值小于当前最大值, 更新答案
	# 因为k越小, 加的w越少, 所以(k-j)/v*w就是补正, 别忘了k要/v才是加的个数 
	# 若是不能理解为什么tail能减得比head还小, 滑动窗口, 请，我也不会证明 
	进元素
	head<=tail, 更新答案 
*/

CSDN排版甚至不如注释好看
封面：https://www.zerochan.net/3165620

欢迎分享，转载请注明来源：内存溢出

原文地址: https://outofmemory.cn/langs/673375.html

赞 (0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
code code 管理员组
0 0
上一篇 2022-04-19
下一篇 2022-04-19

发表评论

登录后才能评论

评论列表（0条）

保存