动态规划是算法中一门很重要的思想，其通过对每一步的假设规划，不停的寻找最优最有利的解决方案，然后一步一步求解出来。
而01背包是其中最基本的一种dp思想，其题目一般为给定一个容量为V的背包，然后有n件物品，其价值为value[i]，每件物品只能最多选择一次或者不选择，问如何才能得到的物品价值最大。
一般dp问题的核心就是一个 状态转移方程 。状态转移方程一出来题目基本上就木得问题了。
通常来说，状态转移方程的代码思想一般如下
for(int i=0; i<n; i++) { for(int j=0; j<=V; j++) { if(j>=v[i]) dp[i+1][j] = max(dp[i][j], dp[i][j-v[i]]+val[i]); else dp[i+1][j] = dp[i][j]; } }
来看看这段代码，将第i件物品放在容量为j的背包中，使得dp[i][j]最大，对于第i件物品来说，有两种选择：
第一，不放这件物品。如果不放这件物品，则dp[i+1][j]=dp[i][j]。
第二，放这件物品。那么首先考虑是否放的下，就是剩下的空间j是否比这件物品的体积v[i]大。
如果大，则在j中腾出v[i]的空间给第i个物品，然后加上其价值与dp[i][j]比较一下就好了，取其中的最大值。
如果j小于v[i]，那么这个物品就不要考虑了，直接丢掉就行了。
先看看基础的题目。
1.hdu 2602
这道题目就是一道裸的不能再裸的01背包，给定的容量V，n件物品，每件价值给定，然后只能选一次。
首先学习到了有两种方法解决这道题，第一种是用二维数组，将每次的中间过程都存储下来，状态转移方程又有两种写法。
1 dp[i+1][j]=max(dp[i][j],dp[i][j-v[i]]+val[i]); 2 3 注意这个是数组从0开始进行for循环 4 5 dp[i][j]=max(dp[i-1][j],dp[i-1][j-v[i]]+val[i]); 6 7 这个是数组从1开始进行for循环 8 9 其中v代表体积，val代表价值
以下是二维数组ac代码：
#include <iostream> #include <algorithm> #include <string.h> #include <stdio.h> #define ll long long int #define inf 1000000007 using namespace std; int main() { int t; int val[1010],v[1010]; int dp[1010][1010]; cin>>t; while(t--) { int n,V; cin>>n>>V; for(int i=0;i<n;i++) cin>>val[i]; for(int i=0;i<n;i++) cin>>v[i]; for(int i=0;i<n;i++) { for(int j=0;j<=V;j++) { if(j>=v[i]) dp[i+1][j]=max(dp[i][j],dp[i][j-v[i]]+val[i]); else dp[i+1][j]=dp[i][j]; } } cout<<dp[n][V]<<endl; } return 0; }
还有另一种的一维数组的代码，一维数组其实就是对上面二维数组的空间优化，具体好像是对空间的一种优化，对于二维数组来说，中间的每一次循环还记录着，而这些数据都是冗余的，可以不用，所以可以用一维数组进行dp。
状态转移方程如下：
for(int i=0; i<n; i++) { for(int j=V; j>=v[i]; j--) { dp[j] = max(dp[j], dp[j-v[i]]+val[i]); } }
为什么要从V开始递减遍历？我举个例子，假设一个物品GG价值1000，体积为2，那么假设我们按【0…..v】这个顺序遍历，那么在j=2时，dp[2] = max(dp[2], dp[0]+1000)，那么dp[2] = 1000，当j=4时，dp[4]=max(dp[4], dp[2]+1000)， dp[4] = 2000，这时我们再思考一下，GG将被放进背包两次了！如果我们逆序遍历，就可以避免这种结果。
以下是一维数组ac代码：
#include<iostream> #include<algorithm> #include<stdio.h> #include<cstring> using namespace std; int main() { int value[1010],dp[1010],v[1010]; int t; cin>>t; while(t--) { memset(dp,0,sizeof(dp)); memset(value,0,sizeof(value)); memset(v,0,sizeof(v)); int n,V; cin>>n>>V; for(int i=0;i<n;i++) cin>>value[i]; for(int i=0;i<n;i++) cin>>v[i]; for(int i=0;i<n;i++) /// i代表的是物体的顺序 { for(int j=V;j>=v[i];j--) //j代表背包剩余的体积 { dp[j]=max(dp[j],dp[j-v[i]]+value[i]); } } cout<<dp[V]<<endl; } return 0; }
2.hdu 2546
某天，食堂中有n种菜出售，每种菜可购买一次。已知每种菜的价格以及卡上的余额，问最少可使卡上的余额为多少。
Input
第一行为正整数n，表示菜的数量。n<=1000。
第二行包括n个正整数，表示每种菜的价格。价格不超过50。
第三行包括一个正整数m，表示卡上的余额。m<=1000。
n=0表示数据结束。
Sample Input
Sample Output
题意大概就是饭卡的钱如果大于5，就能用，小于5就不能刷了，然后可以透支，如果大于5则可以减去一个数得到负值，问如何买使得剩下的钱最少。
题目思路一般就是先用sort把物品价值排个序，然后把最大的记录下来，然后用dp来使得剩余的钱尽可能的少并且大于5元。
ac代码如下：
#include<iostream> #include<algorithm> #include<cstring> #include<stdio.h> using namespace std; int main() { int val[1010],dp[1010]; int n,m; while(cin>>n&&n) { memset(dp,0,sizeof(dp)); memset(val,0,sizeof(val)); for(int i=0;i<n;i++) cin>>val[i]; sort(val,val+n); int maxn=val[n-1]; cin>>m; if(m<5) cout<<m<<endl; else { for(int i=0;i<n-1;i++) //这里要少一个，因为最大的已经记录下来了 for(int j=m-5;j>=val[i];j--) { dp[j]=max(dp[j],dp[j-val[i]]+val[i]); } cout<<m-maxn-dp[m-5]<<endl; } } return 0; }