背包再学习笔记

背包再学习

之前学习的几个背包都是背几个一维数组的板子，没有深入的理解其中的含义，当碰到一个相似的背包的问题时，板子出现了短板，这时就难于写出题目；

先说 01 背包：

一维数组的板子大家都会，这里讲二维：

dp[i][j]=max(dp[i-1][j],dp[i-1][j-v[i]]+w[i]);

这里的 i 表示第几个物品，j表示目前用的背包体积；

还有一个要注意的是背包不只是求max，min照样可以，只是初始化问题，我前面的一篇博客有讲到；

伪代码:

memset(dp,0,sizeof(0));//一般无特殊情况，初始为0 
	for(int i=1;i<=n;i++){//表示有 n 个物品 
		for(int j=0;j<=s;j++){//表示背包体积为 s 
			dp[i][j]=dp[i-1][j];//表示没有取 i 物品
			if(j>=v[i]) dp[i][j]=max(dp[i][j],dp[i-1][j-v[i]]+w[i]);//取了 i 物品 
 		}
	}

再谈完全背包：

学习博客

完全背包和01背包的区别在于一个物品可以取无数个，直到背包装不下；

我们可以很显然的从 01 背包推出表达式：

dp[i][j]=max(dp[i][j],dp[i-1][j-v[i]*k]+w[i]*k) (0<=k * v[i]<=j)

伪代码：

	memset(dp,0,sizeof(0));//一般无特殊情况，初始为0 
	for(int i=1;i<=n;i++){//表示有 n 个物品 
		for(int j=0;j<=s;j++){//表示背包体积为 s 
			int m=j/v[i];//最多能拿几个物品 i  
			for(int k=0;k<=m;k++){
				dp[i][j]=max(dp[i][j],dp[i-1][j-k*v[i]]+k*w[i]);
			} 
 		}
	}

虽然时间和空间复杂度都很大，但是对于我们深刻理解背包，理解动态规划都有很大的意义；