一 二进制与十进制

1. 普通遍历问题

遍历 n 个物品, 采用二进制计数方法遍历与采用十进制技术方法遍历的时间复杂度是一样的

举例来说, 对于十进制数 8

十进制遍历: 0,1,2,3,4,5,6,7 共 8 次遍历

二进制遍历: 000, 001, 010, 011, 100, 101, 110, 111 共 8 次遍历

2. 多重背包问题

同样的道理, 对于多重背包问题, 采用二进制的遍历方法不能优化时间复杂度

优化的原因在于引入了动态规划

二 动态规划的时间复杂度估算

动态规划的时间复杂度 $\approx$ 问题的总个数 $\times$ 问题要做出的选择数

如, 对于 01 背包问题, 问题的总个数为 $N\cdot V$ (N 为物品个数, V 为背包容量), 问题要做出的选择数为 2 (选或不选)

则 01 背包问题的时间复杂度约为 $2N\cdot V$

三 多重背包

如果不采用动态规划的做法, 就像普通的遍历问题那样, 是否采用二进制的计数方法对时间复杂度的优化没有任何关系

但采用二进制的计数方法会影响问题的总个数与问题的选择数的乘积, 即动态规划做法下多重背包的时间复杂度

多重背包的动态规划时间复杂度

十进制遍历方法

问题的总个数为 $N\cdot V$, N 为物品的种类数, V 为背包容量

问题的选择数约为 $S_{max}$, $S_{max}$ 为每种物品数量的最大值

十进制下多重背包问题的 DP 时间复杂度为: $N \cdot V \cdot S_{max}$

二进制遍历方法

十进制下, 一种物品有 $s_i$ 个, 二进制下, 变为 1, 2, … , $\lg s_i$ 个物品, 则共有 $\lg s_1 + \lg s_2 + … + \lg s_n$ 个物品, 约为 $N\lg s_{max}$ 个物品

问题的总个数为 $N\cdot V \cdot \lg s_{max}$

问题的选择数为 2

十进制下多重背包问题的 DP 时间复杂度为: $2N\cdot V \cdot \lg s_{max}$

四 代码实现

#include <iostream>
#include <vector>

using namespace std;

const int N = 2010;
int f[N];
int v[N], w[N], s[N];

vector<pair<int,int>> goods;

int main()
{
    int n, m;
    cin >> n >> m;
    for(int i = 1; i <= n; i++) cin >> v[i] >> w[i] >> s[i] ;
    for(int i = 1; i <= n; i++)
    {
        for(int k = 1; k <= s[i]; k *= 2)
        {
            s[i] -= k;
            goods.push_back({k*v[i], k*w[i]});
        }
        if(s[i] > 0)
        {
            goods.push_back({s[i]*v[i], s[i]*w[i]});
        }
    }

    for(auto good : goods)
    {
        for(int j =m; j >= good.first; j--)
            f[j] = max(f[j], f[j - good.first] + good.second);
    }
    cout << f[m] << endl;
    return 0;
}