背包九讲之01背包

        01背包的问题是背包问题中最基础的，也是学习其他背包类型的前提，新手的时候被背包折磨地死去活来，理解了很久，才慢慢明白其中的原理。因此打卡留个纪念。

        话说有一个给定容量大小capacity的背包，以及一堆物品，每一个物品都有其对应的重量weight和value，为什么是weight，我也不知道。别人都是这么写的，就把weight当做体积来看吧。问对于给定容量的这个背包，能够装下的物品的最大的价值value是多少？

          假如我们把物品放成一排，从左往右开始取。对于给定的容量capacity，我们再依次用1,2，3，....capacity去尝试装每一件物品，看看能否装的下，即计算出每一个容量状态下的背包最大价值，以此推算出状态转移方程。对于当前的一个重量为w,，价值为v的物品，如果我们此刻试探它的容量c1小于w，那么对于当前这个物品我们肯定是拿不了，因为背包全空也装不下。如果我们试探它的容量c1>=w，那么对于当前物品，我们当然可以选择拿，或者不拿。那我们该怎么判断拿还是不拿呢？

        很简单。我们可以保证，当前物品的w一定小于等于此时我们尝试的背包容量c1。如果我们选择拿当前物品的话，背包里就要有w的空间是留给当前物品的，即用我们背包的容量c1减去当前物品的重量，即c2=c1-w，我们可以保证得到的这个c2一定是大于或等于0的，因为我们在进行这一步的前提就是物品的w一定小于等于此时我们试探的背包的容量c1。 意思是在背包里预留出了当前物品的位置，c2表示的是当用我们一开始的试探容量减去预留出当前物品的容量之后，背包里的剩余容量。其实也就是指放下当前物品之前状态的背包容量。要注意的是，当前c2的空间不一定全部装满了，也有可能有一部分多余的空间，但是这个无所谓（当初就这里很不理解）。然后我们再用预留出位置之后的背包里的物品价值+当前物品的价值，与预留出位置之前背包里的物品价值比较，如果前者大于后者，说明我们这一操作有效，因此我们选择拿当前这件物品，如果前者小于后者，则说明我们这一步是没必要的，不选择当前物品。

        众所周知，背包问题要用到动态规划，那我们怎么推导它的状态转移方程呢？我们设dp[i][j]为当遍历完前i件物品，试探物品的背包容量为j时，背包所能装下的物品最大价值。根据刚刚的推算，我们已经知道了对于每一件物品，我们只能选择拿或者不拿，不管我们如何做选择，我们可以得知，我们遍历完当前物品之后的状态（不管是拿还是不拿当前物品），都是由遍历完上一件物品之后的状态得来的。什么意思呢？如果我们试验的背包容量<当前物品的重量的话，当前物品我们只能选择不拿，因此我们遍历完当前物品的dp[i][j]的值，就等于遍历完上一件物品的dp[i-1][j]，即dp[i][j]=dp[i-1[j],因为当前物品我们是没有取的。如果选择拿的话，我们就要预留出当前物品的空间，即上面所说的c2=c1-w, 因此我们就要找到遍历完上一件物品之后，背包容量为c2时的状态（因为在遍历上一个物品的时候，我们也依次用从小到大的背包容量去试探了上一件物品）,即dp[i-1][j-w], 因为选取了当前物品，背包的价值就要加上当前物品的价值，为dp[i-1][j-w]+v，这就是选取背包容量大于当前物品且选取了当前物品之后的背包的价值，根据以上的推算可知：dp[i][j]=max(dp[i-1][j],dp[i-1] [j-w]+v).

        因此我们外部遍历物品，对每个物品，内部还要遍历每一个大小的容量，以此存储每一个容量的状态。代码如下：

#include<iostream>
using namespace std;
const int maxn=1010;
int capacity,w[maxn],v[maxn],n;
int dp[maxn][maxn];
void test_01bag_2wei_dp(){
	//外层遍历物品
	for(int i=1;i<=n;i++){
		//内层遍历背包容量
		for(int j=0;j<=capacity;j++){
            //这一段已经推导过了
			if(j<w[i]){ 
				dp[i][j]=dp[i-1][j];
			}else{
				dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]);
			}
		}
	}
    //最后输出的答案就是当遍历全部n个物品，背包容量为capacity的时候的状态。
	printf("%d",dp[n][capacity]);
}
int main(){
	//n为物品种类,capacity为给定的背包容量
	scanf("%d%d",&n,&capacity);
	for(int i=1;i<=n;i++){
		//每一件物品的重量和价值
		scanf("%d%d",w+i,v+i);
	}
	test_01bag_2wei_dp();
	
	return 0;
}

        关于01背包用二维数组的话是比一维数组更容易理解的，一维数组优化版的话等我歇会再写。