文章内容:

解决dp问题的基础关键:

有限集合求最值:

化零为整,所谓化零为整就是解决问题的时候不是一个元素一个元素的去枚举,而是每次枚举一类东西,一个子集 子集里的一堆元素...这个就可以看作是一个化零为整的过程,就是把一些有相似点的元素划分成一个子集,然后用 某一个状态来表示,这也叫做状态表示。

状态表示:

1、集合:如 f(i),我们要考虑的是 f(i)表示的是哪个集合,这个集合是什么,一般这个集合描述的是所有满足什么 什么条件(题目的条件)的方案的集合,这就是f(i)所表示的方案的集合,正是因为f(i)每次可以表示一类集合,而不是 一个元素,所以它才可以去优化时间复杂度。 例如:一个学校里有2000个人,如果我们要一个一个的去数那么要数2000次,但是如果我们按照一个一个班级去数那就 只需要数20次就行了,这就是优化的核心。

2、属性:一般f(i)里面存的是一个数字,如整数或者浮点数或布尔值,那么存的这个数和这个集合的关系就叫做属性 属性一般有三种\:max(最大),min(最小),count(数量)。

状态计算:

所谓状态计算就是把状态表示的每一个步骤算出来,状态计算一般对应的是一个化整为零的过程。

化整为零:

所谓化整为零就是先看一下f(i)所表示的所有状态是什么,也就是把f(i)划分成若干个部分,然后每一个 部分分别去求,这里把部分叫做子集,这些子集一般要满足两个原则:

1.不重复,就是每一个元素只属于其中一个集合

2.不遗漏,就是这个子集里所有的元素一定是把f(i)里所有的元素都包含了

这样的话当我们想求f(i)的时候只需要分别求出每个子集的值就行了:

比如说f(i)的属性是最大值,那么只需要求出每一个子集的最大值再在这些最大值里取一个max就可以了。

比如说f(i)的属性是数量,那么只需要求出每一个子集的数量再相加就可以了。

注意:不重复这个原则其实可以不遵守,如果是求数量的话才需要遵守这个原则

比如说我们要在三个数 A,B,C里求最大值,那么就先求max(A,B)的最大值,再求max(B,C)的最大值,再把这两个最大 值进行一个比较就可以得到三个数的最大值,这里B就重复被用了两次。

以上就是化整为零的过程。

集合的划分:

一般划分集合的依据是找最后一个不同点

题目1：01背包问题

原题链接

解题思路:

f[i][j]表示只看前i个物品,总体积是j的情况下,总价值最大是多少。 推理:假设在这些物品中有一个特殊的物品 i,那么便有两种情况: 1:不选第i个物品:f[i][j]=f[i-1][j];意思是不选第i个物品只考虑前i-1个物品体积是j的情况下的最大价值 2:选第i个物品:f[i][j]=f[i-1][j-v[i]];意思是选第i个物品那么物品的体积 j就要减去第i个物品的重量因为 既然已经选了第i个物品那么背包就要给它腾空间,所以j要减去v[i],然后既然第i个物品已经被考虑完了,那么 只需要继续考虑前 i-1个物品就好了,所以i要-1。 最终的答案就是在上面两种情况里选一个最大值:f[i][j]=max(1. , 2.); 初始值定为:f[0][0]=0;表示0个物品并且总体积是0的情况下最大价值是0

代码:

#include <bits/stdc++.h>
using namespace std;
#define N 1001
int n, m;
#if 0
因为f[N][N]是定义在全局变量的,全局变量在堆区,堆区默认初始化为0
#endif
int f[N][N];
#if 0
v代表体积,w代表价值
#endif
int v[N], w[N];
int main()
{
    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 = 0; j <= m; ++j)
        {
#if 0
            如果不选
#endif
            f[i][j] = f[i - 1][j];
#if 0
            如果选
            因为只有在第i个物品的重量小于j(背包的容量)的情况下才能选
#endif
            if (j >= v[i])
            {
#if 0
                因为选了第i个物品所以要加上第i个物品的价值
#endif
                f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + w[i]);
            }
        }
    }
    cout << f[n][m] << endl;
    return 0;
}

01背包问题优化:

闫式dp分析法 分析:其问题的本质就是在一个有限集合里求最大值,n是物品的体积是有限的,m是物品的价值也是有限的 v是背包里物品的容量,w是背包里的东西的价值,这些都是有限的 从几个角度看dp: 1.状态表示: 一般来说伴随着选择问题的题目的状态表示第一维都是"只考虑前i个物品"f(i)因为都是只考虑选或不选, 第二维"一般都是几个限制"比如说体积的限制或者重量的限制或者只能选几个的数量的限制等等"f(i,j)" 2.看描述的这个集合是什么: 所有满足条件1,条件2的这个元素的集合,条件就是状态表示里面的条件,那么这里的集合就是: <"所有只考虑前i个物品,并且总体积不超过j的选法的集合。">!!!转换过来就是: 所有从1-n个物品当中选,并且总体积不超过m的选法的集合。 3.属性： 一般看问题问的是什么,那这个值就是什么,在这里问题问的是总价值最大是多少,那么这里的属性是: 集合当中每一个方案的最大价值:max。 4.状态计算: 找最后一个不同点: 所谓最后一个不同点就是我们选最后一个物品的方法,如:选第i个物品和不选第i个物品是两种方案 那么只需要将f(i,j)所表示的集合划分成两个子集: 左边的子集表示在f(i,j)当中所有不选择第i个物品的方案: 左子集在f(i,j)当中,所以它需要满足f(i,j)的限制,也就是说它需要满足:从1~i中选且总体积小于等于j, 并且它要不包含物品i,那么它就变成了从1~i-1中选且总体积小于等于j的方案的集合:f(i-1,j); 右边的子集表示在f(i,j)当中所有选择第i个物品的方案: 右边的子集又可以分为两个小的方案: 1.前面随便选最后一定包含第i个物品,这是不变的部分,那么它的价值就是w[i]。 2.前面不随便选而是在不包含第i个物品的前提下随便选,也就是说第i个物品已经提前内定被放进了背包 那么就需要用j-v[i],j代表背包的容量,v[i]代表物品的重量,然后再在除了这个已经放进背包的v[i]之外 的i-1个物品里面选,并且总体积小于等于(j-v[i])的方案。 那么右边的子集的最大值就是上面两个方案加起来的值,也就是变化部分的最大值加不变的值: f(i-1,j-v[i])+w[i];注意当j

代码:

#include <bits/stdc++.h>
using namespace std;
#define N 1001
int n, m;
int f[N][N];
int v[N], w[N];
int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; ++i)
    {
        cin >> v[i] >> w[i];
    }
#if 0
    因为i要减一,如果从0开始的话会越界
#endif
    for (int i = 1; i <= n; ++i)
    {
        for (int j = 0; j <= m; ++j)
        {
            f[i][j] = f[i - 1][j];
            if (j >= v[i])
            {
                f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + w[i]);
            }
        }
    }
    cout << f[n][m] << endl;
    return 0;
}

题目2：完全背包问题

原题链接

解题思路:

分析:完全背包和01背包的区别就是01背包里一个物品只能拿一次,而完全背包能拿无数次

状态表示:

- 所有满足只从前i个物品中选,且总体积不超过j的方案的集合 - 属性:最大值也就是max

总结:所有满足只从前n个物品中选,且总体积不超过m的方案的集合的最大值

状态计算:

与01背包不同,完全背包不止两个状态子集,而是要定义成多个状态子集:

  • 选0个第i个物品,也就是不选:那么就是从1~i中选并且不选i=>1~i-1<=j=>f(i-1,j);
  • 选1个第i个物品,与第k个物品同理
    • 选2个第i个物品,与第k个物品同理
  • 选k个第i个物品,把上面分成两个状态,第一个状态是固定不变的,也就是选择第k[i]个物品是不变的

    那么不变的物品价值就是w[i];

    第二个状态是变的,选择前面流动的1~k[i-1]个物品是变化的,我们要做的就是在流动k-1个物品里选择最大值

    那么就是在1~i-1里(除了第i个物品)并且<=j-v[i](因为最后背包要给第i个物品腾位置)。

    那么最后这两种状态的公式是:f(i-1,j-v[i])+w[i];(w[i]是固定的要加上)

    ...一直到不能选为止也就是体积超过了j为止

最后把上面的公式都加起来选一个最大值:

因为f(i-1,j-v[i])+w[i]只是第2个集合(选1个第i个物品)的公式,还有剩下的集合的公式要一起加起来 f(i,j)=max(f(i-1,j),f(i-1,j-v[i])+w[i],f(i-1,j-2v[i])+2w[i].....j-kv[i]+kw[i])<=j

优化等差数列消除:

直接将原来公式里的j变成上面公式的第二项j-v[i],那么公式就变成了:

f(i,j-v[i])=max(f(i-1,j-v[i]),f(i-1,j-2v[i])+w,f(i-1,j-3v[i])+2w....))+w[i];

上面的公式的每一项都比原来的公式少了一个w[i],所有最后要加上w[i];

其实也就是把原来的公式从第二项 f(i-1,j-v[i])+w[i],开始变为另外一个公式,而原来的第一项公式 f(i-1,j)只需要在最后求最大值的时候加上就行了。

最终只需要在上面的两个公式中选一个最大值max就是我们要的答案:

f(i,j)=max(f(i-1,j),f(i,j-v[i])+w[i]);

代码:

#include <iostream>
using namespace std;
#define N 1001
int n, m;
int dp[N][N];
int v[N], w[N];
int main()
{
    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 = 0; j <= m; ++j)
        {
            dp[i][j] = dp[i - 1][j];
            if (j >= v[i])
                dp[i][j] = max(dp[i][j], dp[i][j - v[i]] + w[i]);
        }
    }
    cout << dp[n][m] << endl;
    return 0;
}

题目3：多重背包问题 I

原题链接

解题思路:

现在有a件物品，每件物品都有他自己的价值与体积，因为每件只能放一次，那么咱们就按先后顺序一个一个拿起来判断，看能不能装下，若是能装下，看要不要拿，要不要拿肯定是看此时拿了的话能否构成此时的最优解。要判断是否是该状态下的最优解肯定要判断如果将该物品放入刚好满的话，那放他之前的最优解是什么。转换一下思维就是要求以 背包容积-该物品容积 为容积的背包装之前的物品的最优解【并不包括本物品以及之后的物品】。那么咱们就要通过从1遍历背包的容积来判断最优解，这就是所谓的基于之前的数据。 现在总结下思路 咱们要做这道题就要挨个物品判断要不要拿能不能拿，同时通过遍历背包容积判断每个容积下的最优解，以此来判断该种物品究竟拿了能不能带到此时的最优解。用二维数组dp[i-1][x],就可以完美的表示第i件物品之前容积为x时的最优解（第i件物品和它后面的物品都不可能在这个背包）

代码:

#include <bits/stdc++.h>
using namespace std;
#define N 110
int n, m;
int f[N];
int main()
{
    cin >> n >> m;
    for (int i = 0; i < n; ++i)
    {
        int v, w, s;
        cin >> v >> w >> s;
        for (int j = m; j >= 0; --j)
        {
            for (int k = 1; k <= s && k * v <= j; ++k)
            {
                f[j] = max(f[j], f[j - k * v] + k * w);
            }
        }
    }
    cout << f[m] << endl;
    return 0;
}

题目4：多重背包问题 II

原题链接

解题思路:

假设有一组商品，一共有11个。我们知道，十进制数字 11 可以这样表示 11=1011(B)=0111(B)+(11−0111(B))=0111(B)+0100(B) 11=1011(B)=0111(B)+(11−0111(B))=0111(B)+0100(B) 正常背包的思路下，我们要求出含这组商品的最优解，我们要枚举12次（枚举装0，1，2....12个）。 现在，如果我们把这11个商品分别打包成含商品个数为1个，2个，4个，4个（分别对应0001,0010,0100,0100）的四个”新的商品 “, 将问题转化为01背包问题，对于每个商品，我们都只枚举一次，那么我们只需要枚举四次 ，就可以找出这含组商品的最优解。 这样就大大减少了枚举次数。 这种优化对于大数尤其明显，例如有1024个商品，在正常情况下要枚举1025次 ， 二进制思想下转化成01背包只需要枚举10次。 如果仍然不是很能理解的话，取这样一个例子:要求在一堆苹果选出n个苹果。我们传统的思维是一个一个地去选，选够n个苹果就停止。这样选择的次数就是n次 二进制优化思维就是：现在给出一堆苹果和10个箱子，选出n个苹果。将这一堆苹果分别按照1,2,4,8,16,.....5121,2,4,8,16,.....512分到10个箱子里，那么由于任何一个数字 x 都可以从这10个箱子里的苹果数量表示出来，但是这样选择的次数就是 ≤10次 这样利用二进制优化，时间复杂度就从 O(n3) 降到O(n2logS)，从4∗10^9 降到了2∗10^7

代码:

#include <iostream>
using namespace std;

const int N = 12010, M = 2010;

int n, m;
int v[N], w[N]; //逐一枚举最大是N*logS
int f[M];       // 体积<M

int main()
{
    cin >> n >> m;
    int cnt = 0; //分组的组别
    for (int i = 1; i <= n; i++)
    {
        int a, b, s;
        cin >> a >> b >> s;
        int k = 1; // 组别里面的个数
        while (k <= s)
        {
            cnt++;          //组别先增加
            v[cnt] = a * k; //整体体积
            w[cnt] = b * k; // 整体价值
            s -= k;         // s要减小
            k *= 2;         // 组别里的个数增加
        }
        //剩余的一组
        if (s > 0)
        {
            cnt++;
            v[cnt] = a * s;
            w[cnt] = b * s;
        }
    }

    n = cnt; //枚举次数正式由个数变成组别数

    // 01背包一维优化
    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]);

    cout << f[m] << endl;
    return 0;
}