backpack-questions.md

背包问题

有 $$n$$ 种物品，物品 $$j$$ 的重量和价值分别为 $$w_j$$ 和 $$v_j$$ ，如果背包的最大容量限制是 $$m$$ ，怎么样选择放入背包的物品以使得背包的总价值最大？

组合优化问题，设 $$x_j$$ 表示装入背包的第 $$j$$ 个物品的数量，解可以表示为 $$<x_1,x_2,\ldots,x_n>$$ 。那么目标函数和约束条件是：

如果组合优化问题的目标函数和约束条件都是线性函数，称为线性规划。如果线性规划问题的变量 $$x_j$$ 都是非负整数，则称为整数规划问题。背包问题就是整数规划问题。限制所有的 $$x_j = 0 or x_j = 1$$ 时称为0-1背包。

✏ 1、0-1背包【链接】

有n件物品和容量为m的背包，给出每件物品的重量 $$w_i$$ 以及价值 $$v_i$$ ，求解让装入背包的物品重量不超过背包容量，且价值最大 。**特点：**每个物品只有一件供你选择放还是不放。

二维解法：设 $$f[i][j]$$ 表示前 $$i$$ 件物品 总重量不超过 $$j$$ 的最大价值，可得出状态转移方程：

$$f[i][j]=max{f[i-1][j-w[i]]+v[i],\ f[i-1][j]}$$

一维解法：设 $$f[j]$$ 表示重量不超过 $$j$$ 公斤的最大价值，可得出状态转移方程：

$$f[j]=max{f[j],\ f[j−w[i]]+v[i]}$$

{% tabs %} {% tab title="二维解法" %}

int maxValue(std::vector<int>& values, std::vector<int>& weight, int n, int m){
    int dp[n + 1][m + 1];
    memset(dp, 0, sizeof(dp));
    for(int i = 1; i <= n; ++i){
        for(int j = 1; j <= m; ++j){
            if(weight[i] <= j)
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + values[i]);
            else
                dp[i][j] = dp[i - 1][j];
        }
    }
    return dp[n][m];
}

{% endtab %}

{% tab title="一维解法" %}

int maxValue(std::vector<int>& values, std::vector<int>& weight, int n, int m){
    int dp[m + 1];
    memset(dp, 0, sizeof(dp));
    for(int i = 1; i <= n; ++i){
        for(int j = m; j >= 1; --j){
            if(weight[i] <= j)
                dp[j] = max(dp[j], dp[j - weight[i]] + values[i]);
        }
    }
    return dp[m];
}

{% endtab %} {% endtabs %}

****Partition Equal Subset Sum****

✏ 2、完全背包【链接】

有 $$n$$ 件物品和容量为 $$m$$ 的背包，给出每件物品的重量 $$w_i$$ 以及价值 $$v_i$$ ，求解让装入背包的物品重量不超过背包容量，且价值最大 。特点：每个物品可以无限选用。

一维解法： 设 $$f[j]$$ 表示重量不超过 $$j$$ 公斤的最大价值，可得出状态转移方程：

$$f[j]=max{f[j],\ f[j−w[i]]+v[i]}$$

int maxValue(std::vector<int>& values, std::vector<int>& weight, int n, int m){
    int dp[m + 1];
    memset(dp, 0, sizeof(dp));
    for(int i = 1; i <= n; ++i){
        for(int j = weight[i]; j <= m; ++j){
            dp[j] = max(dp[j], dp[j - weight[i]] + values[i]);
        }
    }
    return dp[m];
}

****Coin Change****

****Coin Change 2****

✏ 3、多重背包**【链接】**（京东笔试）

有 $$n$$ 件物品和容量为 $$m$$ 的背包。给出每件物品的数量 $$s_i$$ 、重量 $$w_i$$ 以及价值 $$v_i$$ ，求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。特点： 每个物品都有了一定的数量。

二维解法：把 $$s_i$$ 个物品逐个拆分，则得到 $$\sum s_i$$ 个物品，原问题转化为01背包问题，时间复杂度为 $$O(m\times \sum s_i)$$ 。也可以在转移得过程中枚举 $$k$$ ，代表第 $$i$$ 个物品选取的数量，则转移方程为：

$$f[i][j]=\mathop{max}\limits_{0\le k \le s[i]}{f[i - 1][j - k\times v[i]] + k\times w[i]}$$

一维解法：设 $$f[j]$$ 表示重量不超过 $$j$$ 公斤的最大价值，可得出状态转移方程：

$$f[j] = \mathop{max}\limits_{0\le k \le s[i]}{f[j−k\times w[i]]+k\times v[i]}$$

int maxValue(std::vector<int>& values, std::vector<int>& weight, 
             std::vector<int>& count, int n, int m){
    int dp[m + 1];
    memset(dp, 0, sizeof(dp));
    for(int i = 1; i <= n; ++i){
        for(int j = m; j >= weight[i]; --j){
            for(int k = 0; k <= count[i]; k++){
                if(j - k * weight[i] < 0)
                    break;
                dp[j] = max(dp[j], dp[j - k * weight[i]] + k * values[i]);
            }
        }
    }
    return dp[m];
}

优化：

1、二进制优化

将第 $$i$$ 种物品分成若干件物品，可以有 $$(v_i,w_i),(v_i\times 2,w_i\times 2),(v_i\times 4,w_i\times 4)\ldots$$ 等等，每件物品有一个系数，分别为 $$1,2,4,\ldots,2^{k - 1},n-2^k+1$$ ， $$k$$ 是满足的最大整数。例如， $$n$$ 为13，拆分成 $$1,2,4,6$$ 四件物品，根据二进制的性质， $$0\ldots 13$$ 都可以由这四件物品组合得到。于是， $$n$$ 件物品，就拆分成至多 $$logn$$ 件物品。再转化为01背包问题求解，复杂度降至 $$O(m\times \sum logn)$$ 。

int maxValue(std::vector<int>& values, std::vector<int>& weight, 
             std::vector<int>& count, int n, int m){
    vector<pair<int, int> > lis;
    lis.push_back({0, 0});
    int idx, c;
    for(int i = 1; i <= n; ++i){
        c = 1;
        while(count[i] - c > 0){
            count[i] -= c;
            lis.push_back({c * values[i], c * weight[i]});
            c *= 2;
        }
        lis.push_back({count[i] * values[i], count[i] * weight[i]});
    }
    int dp[m + 1];
    memset(dp, 0, sizeof(dp));
    for(int i = 1; i <= lis.size(); ++i){
        for(int j = m; j >= lis[i].second; --j){
            dp[j] = max(dp[j], dp[j - lis[i].second] + lis[i].first);
        }
    }
    return dp[m];
}

2、单调队列优化

将背包的容量按照的剩余分成组：

仔细观察转移方程，会发现真正的转移只会发生在同一组内，不同的组是不可能转移的可以改一下上面的转移方程：

$$f[b+x\times v[i]] = \mathop{max}\limits_{0\le k \le s[i]}{f[b+(x-k)\times v[i]]+k\times w[i]}$$

令 $$t = x - k$$ ，状态转移方程变成：

$$f[b+x\times v[i]] = \mathop{max}\limits_{x-s[i]\le t \le x}{f[b+t\times v[i]]-t\times w[i]} + x\times w[i]$$

这里的转移实际上一对 $$(b,x)$$ 唯一对应一个 $$j$$ 。我们固定 $$b$$ ，那么对于 $$x$$ 的决策 $$t$$ 的集合正好是一个滑动区间，而 $$max$$ 里面是一个和 $$x$$ 无关的式子，所以可以用单调队列来维护。具体算法如下：

• 枚举一个 $$i$$ 和 $$b(0\le b\le v[i])$$ ；
• 从小到大枚举 $$x$$ ，并且用单调队列来维护 $$f[b+t\times v[i]]-t\times w[i]$$ 关于 $$t$$ 单调下降，更新 $$f[b+x\times v[i]]$$ 的值。

由于每个剩余类最多只有 $$\frac{m}{v[i]}$$ 个元素，那么对于一个 $$i$$ ，转移的总时间为 $$O(\frac{m}{v[i]} \times v[i]) = O(m)$$ ，所以算法的时间复杂度为 $$O(n\times m)$$ ，这样我们就又优化掉了多重背包中的物品个数这一维。

int maxValue(std::vector<int>& values, std::vector<int>& weight, 
             std::vector<int>& count, int n, int m){
    int dp[m + 1];
    int q[m + 1];
    int num[m + 1];
    memset(dp, 0, sizeof(dp));
    int l, r;
    for(int i = 1; i <= n; ++i){
        int c = min(count[i], m / weight[i]);
        for(int b = 0; b < weight[i]; b++){
            l = r = 1;
            for(int t = 0; t <= (m - b) / weight[i]; t++){
                int tmp = dp[t * weight[i] + b] - t * values[i];
                while(l < r && q[r - 1] <= tmp)
                    r--;
                q[r] = tmp;
                num[r++] = t;
                // 滑动区间长度不大于c，因为dp[t * weight[i] + b] - t * values[i]既然存在，
                // 那么再加c区间的t * values[i]的值肯定能取到
                while(l < r && t - num[l] > c)
                    l++;
                // 因为dp中的是t * weight[i] + b,所以是q[l] + t * values[i]
                dp[t * weight[i] + b] = max(dp[t * weight[i] + b], q[l] + t * values[i]);
            }
        }
    }
    return dp[m];
}

****Ones and Zeroes