em…今天学习了一下动态规划的0/1背包，发现是真的难啊，本蒟蒻学了8个小时候终于搞明白了，现在写下这篇博客分享一下我对0 / 1背包的讲解，很适合动态规划入门选手（我就是）。
em…动态规划呢，分为线性动规、树形动规、背包动规、区间dp等，树形动规我有写过一篇，今天想写一下0 1 背包的动态规划。首先动态规划应该满足几个条件：最优子结构、有重叠子问题、无后效性质。
直接拿个例子吧。
Bone Collector

Problem Description
Many years ago , in Teddy’s hometown there was a man who was called “Bone Collector”. This man like to collect varies of bones , such as dog’s , cow’s , also he went to the grave …
The bone collector had a big bag with a volume of V ,and along his trip of collecting there are a lot of bones , obviously , different bone has different value and different volume, now given the each bone’s value along his trip , can you calculate out the maximum of the total value the bone collector can get ?

Input
The first line contain a integer T , the number of cases.
Followed by T cases , each case three lines , the first line contain two integer N , V, (N <= 1000 , V <= 1000 )representing the number of bones and the volume of his bag. And the second line contain N integers representing the value of each bone. The third line contain N integers representing the volume of each bone.

Output
One integer per line representing the maximum of the total value (this number will be less than 231).

Sample Input
1
5 10
1 2 3 4 5
5 4 3 2 1

Sample Output
14

题目的意思是：给你一个容量为v的背包，问怎样装物品i，使得它的价值最大。
首先我们可以先将问题划分为n个子问题，从简单的求，往后面推，能够得到最优解。譬如：当n=5时，我们只考察n=1即只有一件重量为w【i】，价值为v【i】的物品，让它遍历整个背包，我们能够得到一个最优解，然后我们把这个最优价记录在数组里面，然后我们考察n=2时的最优解，一直这样进行最后会得到一个全局最优解。
0 / 1背包有一个特点，就是你给我一件物品，那么我面对这件物品，有两种选择：
1：选
选：怎么选
2：不选
下面我给出具体步骤：
当物品只有一件的时候，即i=1：

这时，只有一件物品的最优价值求出来了，我们在考察有两件物品的时候，即i=2：

当i=3时候：

最后我们直接给出i=5的时候（记住我们这里是先对物品做遍历，也可以先对容量做遍历的）

ok我们把基本原来了解之后直接给出状态转移方程：
dp[i][j]=max(dp[i-1][j],v[i]+dp[i-1][j-w[i]])
下面给出ac代码（c++）：

#include<iostream>
#include<algorithm>
#include<string.h>
#define max1 1005
using namespace std;

int dp[max1][max1];//行表示背包容量限制性的最大价值 列表示背包的容量最大价值 

int main()
{
    int v[max1];
int w[max1];
    int n;
    cin>>n;
    while(n--)
    {
        int num,ve;
        cin>>num>>ve;//num件物品 背包的容量ve 
        for(int i=1;i<=num;i++)cin>>v[i];
        for(int i=1;i<=num;i++)cin>>w[i];
        memset(dp,0,sizeof(dp));
        for(int i=1;i<=num;i++)
        {
            for(int j=0;j<=ve;j++)
            {
                if(w[i]<=j)
                {
                    dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]);
                }
                else{
                    dp[i][j]=dp[i-1][j];
                }
            }
        }
        cout<<dp[num][ve]<<endl;
    }
    return 0;
}

注意这里有个坑，就是当你是0个背包的时候也要考虑，这个确实有点难以理解。
然后我再解释一下核心代码：
if(w[i]<=j)
因为是0 1 背包所以肯定会有装与不装的选择 这个判断条件之前已经说过了，只有当我容量足够我才能装，还要考虑一下怎么***r> dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]);
这句就是全局核心代码，解释了怎么装：dp[i-1]表示上一行，你会发现上一行都是子结构最优解，然后现在我背包足够装多件物品，我是选择装还是不装，就看这句语句：max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]);选择最大的价值装，但是如果我当前背包装不下怎么办呢？j-w[i]]这句语句保证了我当前的背包是一定能装的，装不了就是j<w[i]这个会越界，结果是0值，0+v[i]就表示了我现在的背包不足够装下你。
dp[i][j]=dp[i-1][j];
这句话还是比较好理解吧 不装我就赋0值.

以上是我对0 1 背包的理解 ，写此博客纯粹为了加深记忆，如果有什么地方理解不到位，欢迎指教。