01背包

01背包描述

有N件物品和一个容量为V的背包。第 i 件物品的重量是c[i],价值为 w[i]。求解将那些物品装入背包可以使价值最大。

但是为什么会叫它01背包呢？其实这里的01指的是状态，当把物品装进去那么状态就是1，不装就是0.

解决思路

01背包问题其实就是动态规划，那么解决动态规划的思路就一个，找到状态转移方程即可。

那么01背包的状态转移方程是：

dp[i][j] = max(dp[i-1][j],dp[i-1][j-weight[i]]+value[i])

dp[i][j]表示的就是第i个物品，重量为j的物品价值。那么从哪几个状态可以转化到这个状态呢。有两个:

1. dp[i-1][j]不把第i件物品放入背包。
2. dp[i-1][j-weight[i]]+value[i]把第i件物品放入背包。

多说无益，直接上代码：

int dp[100][100] = {0};//记录每种情况下物品总价值
int wight[100];//每种物品的重量
int value[100];//每种物品的价值

for(int i=1;i<=50;i++)//50种物品
{
    for(int j = 0;j<=80;j++)//背包可称重80
    {
        if(j>weight[i])
        {
            dp[i][j] = max(dp[i-1][j],dp[i-1][j-weight[i]]+value[i])
        }
        else
        {
            dp[i][j] = dp[i-1][j];
        }
    }
}

reuturn dp[50][80];

但是我们可以发现我们定义了一个二维数组，如果数据很大时，对内存的开销极大。为此我们可以使用滚动数组，简而言之滚动数组就是用后一个状态覆盖前一个状态。

for(i=1; i<=n; i++)
{
    for(j = m;j>=wight[i];j--)
    {
        dp[j] = max(dp[j],dp[j-weight[i]]+value[i]);
    }
}
reuturn dp[m];

出看可能有点难以理解，不过仔细研究发现内层循环每一次循环都是放第 i个物品的过程。每一次循环后得到一个一维数组 dp[m]。每个数组元素保存的就是放入第i个物品后的物品总价值。所以每次循环利用这个一维数组，滚动变成了二维数组。

其实还有完全背包和多重背包的问题，这里不做细说。