01背包问题（二维数组解法以及一位数组优化）

题目如下：

这个是本人最近接触的动态规划（dp）的一个基础题。

关于动态规划本人也只是有些许浅薄的理解，所以各位可以通过这篇文章来理解什么是动态dp

转自原文：http://www.cnblogs.com/sdjl/articles/1274312.html

那么回归正题，01背包二维数组应该怎么写呢？

我们根据题目，设置定义N为1005，定义二维数组f[N][N]（列数下表用来记录放了几个物品，而列数下标表示背包体积，而这个数组记录的数值就是背包所有物品的价值），定义v[N],w[N],分别表示物品的体积以及物品的价值。

接下来我们讲下思路。

当我们的二维数组到达 f [ i ][ j ]时表示前 i 个物品，总体积为 j 的情况下，背包内的总价值；

而当我们选到了第 i 件物品的时候，我们有两种情况，一个是选择这件物品，一个是不选择该物品，这样我们需要一个限制条件来判断到底要不要选择该物品，而这个条件相信大家都会想到，那就是当选择到第 i 给物品的时候，我们背包的容积应该要大于等于该物品的体积，但是我们这里还有一个问题；

比如，我们背包的大小为5，而我们有两件物品，一个体积为3，价值为4，而另一个体积为5，但价值为5，我们根据最优选择，肯定会选择第二个，因此我们需要涉及一个问题，那就是比较丢掉背包的物品拿另一个物品后，背包内部的总价值和没拿新的物品放进背包的价值，来比较两者大小；

而这个问题，其实特别简单，当我们的 j 小于第 i 个物品的体积的时候，就让 f [ i ][ j ]记录 f [ i - 1] [ j ]  的大小，这样就是记录下还不够体积时的背包内部价值，而当 j 大于等于第 i 个物品的体积的时候，我们就让 f [ i ][ j ]和 f [ i - 1][ j-v[ i ] ]+w[ i ]来比较 ，这样我们就知道到底要不要拿这个物品了。

之后我们就只需要在第 n 行时枚举一下，找到里面的最大值就行了

代码如下 :

#include<stdio.h>
int main()
{
    int n,m;//n表示物品数量，m表示背包体积
    int f[1005][1005];
    int v[1005], w[1005];
    scanf("%d%d",&n,&m);
    int i = 0,j = 0;
    for(i = 1;i <= n;i++)
    scanf("%d%d",&v[i],&w[i]);//v表示物品体积，w表示价值
    f[0][0] = 0;//初始化
    for(i = 1;i <= n ;i++)
        for(j = 0; j<=m ;j++)
            {
                f[i][j] = f[i - 1][j];
                if(j >= v[i])
                    {
                        f[i][j] = fmax(f[i][j],f[i - 1][j - v[i]]+w[i]);
                    }
            }
        int max = 0;
        for(i = 1;i <= m;i++)
        {
            max=fmax(max,f[n][i]);
        }
        printf("%d",max);
    return 0;
}

如果大家对这里还有疑惑，也可以画一个图，简单的理解一下。

比如下面，我们输入四个物品，设置背包最大体积为10；根据状态转移方程，能够得出下图：

这个重点需要理解的是状态转移方程，这个状态转移方程先记录下当 背包容积不够时的总价值，然后当背包容积够的时候就能够根据之前保存的值来直接进行相关的运算，这样就能够直接判断需要拿哪些数据，需要丢掉哪些数据。

接下来时一维数组优化，一维数组优化方法实际上时通过滚动数组，每次到了一个新物品的选择环节是，就刷新滚动数组的值，来将最优解记录下来.

细心的小伙伴应该能够发现，这个二维数组实际上只和它的 j 有关，但是如果去除了 i 列（后无效性原则，只与上一条的数据有关），我们就无法来通过前面的数来判断是否取得该数，那么我们就只能从后往前来一个一个排，代码如下：

#include<stdio.h>
#define N 1005
int f[N];
int n,m;//n为物品的个数，m为背包大小
int v[N],w[N];
int fmax(int a, int b)
{
    return a > b ? a : b;
}
int main()
{
    int i = 0, j = 0;
    scanf("%d%d", &n, &m);
    for (i = 1; i <= n; i++)
        scanf("%d%d", &v[i], &w[i]);
    for (i = 1; i <= n; i++)
    {
        for (j = m; j >= 1; j--)//只有剩余容量大于这个物品的容量时，才能拿下这个物品
        {
            f[j] = fmax(f[j], f[j - v[i]] + w[i]);//将拿下这个物品和没拿下这个物品时的价值相比较，选择价值最大
        }
    }
    printf("%d", f[m]);
    return 0;
}

我这只是一些浅薄的知识，若有没有说明白的地方希望各位多多包涵。