【算法教程】【C/C++】DP(动态规划):背包DP——程序设计思路与代码实现

faryou3个月前 (08-19)技术教程

前言

        上一篇文章中我们学习了简单DP,今天我们来学习一种也很常见的DP——背包DP。


程序设计思路

        背包DP以01背包和完全背包为基础,其他的背包DP都由这两种延伸出去,先看01背包:

        01背包是最简单的背包DP,它是指有n样物品,第i样物品的价值为xi,所占用的容量为yi,你有一个容量为m的背包,要求你用这个背包装下价值最高的物品,每种物品只能装一次。这里每样物品的状态都只有装或不装。故我们可以列出状态转移方程:f[i][j]=max(f[i-1][j],f[i-1][j-yi]+xi(f[i][j]表示在第1到第i个物品中选容量为j的物品能获得的最多的价值)。

        完全背包与01背包的区别在于它每样物品可以选无数次,但它的状态转移方程和01背包有不同。我们可以列出状态转移方程:f[i][j]=max(f[i-1][j-k*yi]+k*xi)(这里的k是指购买了k件i物品,是for循环中的变量),这样做的时间复杂度为O(n3),明显偏慢了。但是我们还有下面的优化:f[i][j]=max(f[i-1][j],f[i][j-yi]+xi),因为我们在进行这次转移前就已经充分的考虑了。这个优化必须自己想清楚。


代码实现

        来看一个01背包问题:

IMG_20240823_190043.png

        很明显,这是一道背包题。直接看代码:

#include <bits/stdc++.h>

int n,m,a[105],dp[105][1005];//n、m、a如题意,dp指上文中i

int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	for(int i=1;i<=n;i++) for(int j=1;j<=m;j++){//分类讨论,判断能不能买
		if(j==a[i]) dp[i][j]=dp[i-1][j]+1;
		if(j>a[i]) dp[i][j]=dp[i-1][j]+dp[i-1][j-a[i]];
		if(j<a[i]) dp[i][j]=dp[i-1][j];
	}
	printf("%d",dp[n][m]);
	return 0;
}

        DP注重的是自己的理解,而且讲解无法达到很好的效果,请自行理解源码~


结语

        背包问题是DP中较为简单的一类,要想学好DP,就应该多刷题,以此总结经验。我是faryou,再见!

本文链接:https://blog.faryou.eu.org/post/106.html 转载需经作者授权!

分享到:

扫描二维码推送至手机访问。

版权声明:本文由faryou的博客发布,如需转载请注明出处。

本文链接:https://blog.faryou.eu.org/post/106.html

标签: C++算法基础
分享给朋友:

发表评论

访客

◎欢迎参与讨论,请在这里发表您的看法和观点。