文档：背包九讲.pdf
链接：http://note.youdao.com/noteshare?id=dd46943fcb36d17dc2cf8a8badac1eb8&sub=6BCF3F133CA44BAC917F07D6D2CA43BA

01背包问题就是：有n个物品，你有个容量为vol的背包，每个物品都有其价值w，和体积v。每个物品都只能拿一次，请问最多能拿多少价值的物品。

输出最大价值。

提供两段代码：一个是未优化过空间复杂度的二维的DP，一个是优化过的一维的。

二维：

//01背包问题之二维DP（空间未优化） 
//https://www.luogu.com.cn/problem/P1048
#include<iostream>
using namespace std;
const int N=1007;
int n,vol,dp[N][N];
struct Objs{
	int w;
	int v;
}obj[N];
void input(){
	cin>>vol>>n;
	for(int i=1;i<=n;i++){
		cin>>obj[i].v>>obj[i].w;
	}
}
void init(){return;}
void dpfun(){
	for(int i=1;i<=n;i++){
		for(int j=1;j<=vol;j++){
			if(obj[i].v>j){
				dp[i][j]=dp[i-1][j];
				continue;
			}
			dp[i][j]=max(dp[i-1][j-obj[i].v]+obj[i].w,dp[i-1][j]); 
		}
	}
}
void output(){
	cout<<dp[n][vol];
}
int main(){
	input();
	init();
	dpfun();
	output();
	return 0;
}

动态规划就是要首先设定状态，然后根据之前的状态，推导出后面的状态，每次推导的过程叫做状态转移，有一个状态转移方程。

而这里我们设立状态的一个方法，就是拿子问题来设置，dp[i][j]想到于n=i;vol=j;时的答案。

状态转移方程就是：dp[i][j]=max(dp[i-1][j-obj[i].v]+obj[i].w,dp[i-1][j]);，要注意的事，要看一下j-obj[i].v不能让他到-1，需要加个判定。

其中obj[i]为第i个物品的信息，包括w价值和v体积。

一维：

//P1048 [NOIP2005 普及组] 采药
#include<iostream>
using namespace std;
const int N=1007;
int vol,n,dp[N];
struct Objs{
	int w;
	int v;
}obj[N];
void input(){
	cin>>vol>>n;
	for(int i=1;i<=n;i++){
		cin>>obj[i].v>>obj[i].w;
	}
}
void init(){
	return;
}
void dpfun(){
	for(int i=1;i<=n;i++){
		for(int j=vol;j>0;j--){
			if(j<obj[i].v) continue;
			dp[j]=max(dp[j],dp[j-obj[i].v]+obj[i].w);
		}
	}
}
void output(){
	cout<<dp[vol];
}
int main(){
	input();
	init();
	dpfun();
	output();
	return 0;
}

代码的改变是：只存dp[vol]，且倒序进行。

我们来解释一下，请看上面的图片，纵轴是1-n，横轴是1-vol。如果obj[4].v=3，则红色格子由两个绿色格子转移得到。

我们发现：不管obj[4].v的值是多少，我们一定是由红格子上面一行，红格子左边的列转移过来的。所以其他部分的数据我们都用不上！我们只要存一行多就够了。因为每次状态转移用到的事红格子左边的数据，所以我们内循环倒序枚举，从右边往左走，要不然如果从左边走会覆盖掉原来的数据，导致最后的结果其实是每个物体都能拿无穷遍。

这里顺便提一句。每个物品的枚举都是独立的，所以可以把能拿无数个的物品和能拿一个的物品都放到一起看。只要让无数个的正序，一个的倒序就好了。

还有对于限定数量的，最简单的就是：比如13个(w=2,v=3），拆开来变成13个单独的，一个个枚举就好了。

但是我们还没有利用它的性质：就是这13个其实是一样的。我们还可以把它类似于写成二进制。假设有 1101（二进制）个(w=2,v=3)，我们可以把它拆成成：(w=22^3,v=3*23)(w=22^2,v=3*22)(w=2*2^0,v=2*20)这3个物品，这样你发现就可以全部覆盖了。这样就从要拆成K个变成拆成logK个了

这感觉有点像快速幂的那个东西……

我想想好像拆成3进制就不行了，就是111，也就是拆成9个，3个，1个。其实你会发现这样需要除了最大的那个每个有1个就可以，其他的都需要有2个，这大概就是因为3进制有0,1,2三个数字，而二进制有只有0和1。而01背包只有选择或者不选，所以，2进制最为契合，毕竟不管我们怎么拆，最后拆出来的，都是一个只能选或不选的，只有两个状态的“物品”。