DP——背包问题基础(01背包)

写在最前面

问题背景自行查阅核心思路：状态迭代的过程初始化二维到一维的转换（细节的理解） 以下内容为c++语法

二维

n为物品个数，m为背包容量 v[i]--->体积，w[i]--->价值状态f[i][j]代表拥有前i个物品且背包容量为j下的最优解(价值最高）。

迭代过程如下： 对应f[i][j]来说，相当于f[i-1][j]情况下再加入了一个新物品，因此我们可以选择加入或者不加入新的物品 如果不加入： 则有f[i][j] = f[i-1][j] 如果加入： 则有f[i][j] = f[i-1][j-v[i]]+w[i] 对此，我们取两者的较大值即可 Result = MAX( f[i-1][j] , f[i-1][j-v[i]]+w[i] )

初始化

f[0][0] = 0或者直接定义全局变量数组->全部初始化为0

细节

结果不需要从0开始遍历，因为f[n][m]就是结果哪怕最大值有多个地方出现，最后的f[n][m]也一定是最大值,因为状态可以迭代过来

代码（二维）

#include<bits/stdc++.h>

using namespace std;

const int MAXN  =  1005;
int v[MAXN];    // 体积
int w[MAXN];    // 价值 
int f[MAXN][MAXN];  // f[i][j], j体积下前i个物品的最大价值 

int main() 
{
    int n, m;   
    cin >> n >> m;
    for(int i  =  1; i < =  n; i++) 
        cin >> v[i] >> w[i];

    for(int i  =  1; i < =  n; i++) 
        for(int j  =  1; j < =  m; j++)
        {
            //  当前背包容量装不进第i个物品，则价值等于前i-1个物品
            if(j < v[i]) 
                f[i][j]  =  f[i - 1][j];
            // 能装，需进行决策是否选择第i个物品
            else    
                f[i][j]  =  max(f[i - 1][j], f[i - 1][j - v[i]] + w[i]);
        }           

    cout << f[n][m] << endl;

    return 0;
}

此处数据样例：5 10
1 5
2 4
3 3
4 2
5 1

->14

优化-->二维转一维

代码（一维）

//省略了输入输出,只保留处理部分
for(int i  =  1; i < =  n; i++)
{
    for(int j  =  m; j > =  v[i]; j--)  
        f[j]  =  max(f[j], f[j - v[i]] + w[i]);
}

三个问题：

为什么可以转一维？ 因为我们只需要求出当前 n,m 下的最优解即可，而f[i][j]的二维形式可以作为求出任意 i,j 下的解所以可以转化为一维进行求解

为什么要逆序（j从m开始 j--)？ 因为假设当前的状态是i 那么f[j-v[i]]必定在f[j]前已经计算过，此时算出来的f[j-v[i]]等价于二维时的f[i][j-v[i]] 即迭代到i时，我在j-v[i]的容积下可能已经装入过第i个物品，因此，如果此时在j时装入第i个物品，f[j-v[i]]+w[i]是失效的，因为f[j-v[i]]已经用第i个新物品装过了，俗称被污染了所以，如果我们倒序遍历的话就可以做到，f[j]装入第i个物品时使用还没被污染的f[j-v[i]]即二维状态下的f[i-1][j-v[i]]

为什么要从判断条件为j> = v[i]？ 因为当我们在循环中做判断时，

if(j<v[i])
f[j] = f[j] //（一维）
// 即 f[i][j] = f[i-1][j] (二维）
所以一维状态下，这句话是可以省略掉的
if(j> = v[i])
f[j] = f[j-v[i]]+w[i]

既然 j 只在j> = v[i]时变化，那么可以在循环中修改判断条件让 j 从 m 倒序到 v[i] 即可，因为再减下去结果也不会变化

其他

特殊优化

有些题目在特定优化下可以做到一边输入一边处理但由于数据的不同例如： 可以同时输入价值和体积 1 5 2 4 3 3 4 2 5 1 也可以先输出完所有价值，再输出所有体积 1 2 3 4 5 5 4 3 2 1 前一类数据输入方式可以进行优化处理，后一类不行，因此不再过多介绍新的优化方式，仅提供前一类的优化代码

for(int i  =  1; i < =  n; i++) {
        int v, w;
        cin >> v >> w;      // 边输入边处理
        for(int j  =  m; j > =  v; j--)
            f[j]  =  max(f[j], f[j - v] + w);
    }

对逆序的其他解释

如果使用顺序，会先更新f[4],再更新f[7]，对于这个书包问题来讲，就是有可能，在更新f[4]的时候，已经把这次能加的物品加进来了，然后更新f[7]的时候，还有可能再加一次，所以必须使用逆序，保证，f[4]是没有加入新物品前，背包里的最优解。

若j从小到大，f[j-v[i]]中，由于j-v[i]小于 j ，f[j-v[i]]已经在i这层循环被计算了，而我们想要的f[j-v[i]]应该是 i-1 层循环里面的，所以j从大到小的话保证此时的f[j-v[i]]还未被计算，也就是第 i-1 层的数据

thanks for reading , your comments are appreciative