完全背包告诉你 2020 代表什么

 

上周大家都在玩一个梗,就是对 2020 有如下分解。

之后大家对 2020 的分解也纷纷作出了自己的各种各样的解释,例如:2020 毕竟是不平坦的一年,程序员要 996 之类的。当然其中还有一些朋友还作出了一种有趣的分解:

\[2020=404+404+404+404+404\]

果然 2020 是码农们难过的一年啊。 看了这些调侃的帖,其实身为工程师的我第一个考虑到的问题问题是,如何求解 2020 所有的和数分解(感觉很无聊的样子)?这种方法能不能上升到一个通解问题,例如给出一个年份,让我求解所有与程序员相关数字的加和组合,是不是可以拼凑出这个数字?

围绕这个问题,我们这篇文章来讲讲一个有趣的动态规划问题:完全背包问题

深度优先搜索

其实抽象出这个问题后,我们脑海中第一个出现的思路就是使用深度优先搜索来解决它。当然在这之前,我们要做一些逗比的准备,例如我编了一些代表特殊含义的数字,比如 404500 这种常见的 HTTP 返回错误码,251996965 这种最近很火的几个词,以及 31 代表一个月,1024 代表程序员。接下来就是代码实现了。想法和思路很简单,只要每次取一个数字,然后不断的去递归尝试即可解决这个问题:

#include <iostream>
#include <vector>
using namespace std;

vector<int> w {31, 251, 404, 500, 965, 996, 1024};

void dfs(int cur, vector<int> cur_res, int index) {
    if (cur == 0) {
        for (int i = 0; i < cur_res.size(); ++ i) {
            cout << cur_res[i] << " ";
        }
        cout << endl;
        return;
    }
    if (cur < 0) return;
    for (int i = index; i < w.size(); ++ i) {
        if (cur - w[i] >= 0) {
            vector<int> nxt(cur_res);
            nxt.push_back(w[i]);
            dfs(cur - w[i], nxt, i);
        }
    }
}

int main() {
    vector<int> a;
    dfs(2020, a, 0);
}

// 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 404 500
// 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 251 404 404
// 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 404 965
// 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 404 996
// 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 500 1024
// 31 31 31 31 31 31 31 31 31 31 31 251 404 1024
// 31 965 1024
// 404 404 404 404 404
// 996 1024

但是,这种方法只是一种低效率方法,因为它会遍历所有的结果树将所有结果全部枚举出来处理。其实这也就是深度优先搜索的劣势特点。有没有更加优化的方式来处理这个问题呢?

完全背包问题

我在之前的文章中讲过 01 背包问题,其实就是通过构造当前背包容量的子状态,从而通过动态规划来解决问题。

在这个问题中,我们来做一次模型的抽象:我们要求解指定数字要组成目标值的和的各种组合,如果将这些数字的权值和体积都使用这些数字的本身来描述,是不是就变成了一个恰好装满背包的那种问题? 由于这些数字的数量是没有个数限制的,区别于所有物品数都是 1 的 01 背包,这种情况下的问题又被称为 完全背包问题

如果你拥有 01 背包的基础,完全背包的理解也就非常简单了。因为状态转移方程是相同的,唯一的区别就是在对体积遍历的时候,我们从当前选取物品的体积 正向遍历到背包总体积 即可。原因就是因为个数是无限的,有就可以往里装。

另外,恰好背满我们需要初始化所有状态都为负无穷,而 dp[0] = 0 。这个也在上一个 01 背包问题的文中有讲过。下面来看代码实现:

#include <iostream>
#include <string.h>
#include <vector>
using namespace std;

int dp[2050];
bool choice[2050][2050];
vector<int> w {31, 251, 404, 500, 965, 996, 1024};
int V = 2020;

void dfs(int v, vector<int> current) {
    if (v == 0) {
        for (int i = 0; i < current.size(); ++ i) {
            cout << current[i] << " ";
        }
        cout << endl;
        return ;
    }
    if (v < 0) return;
    for (int i = 1; i <= w.size(); ++ i) {
		// 由于使用 choice 来记录选取,所以我们可以多做一层剪枝
        if (choice[i][v] && v - w[i - 1] >= 0) {
            vector<int> nxt(current);
            nxt.push_back(w[i - 1]);
            dfs(v - w[i - 1], nxt);
        }
    }
}

#define INF -10000000

int main() {
    for (int i = 1; i <= V; ++ i) {
        dp[i] = INF;
    }
    dp[0] = 0;
    memset(choice, 0, sizeof(choice));
    for (int i = 1; i <= w.size(); ++ i) {
        // 这里与 0-1 背包有遍历顺序的差异
        for (int j = w[i - 1]; j <= V; ++ j) {
            if (dp[j - w[i - 1]] >= 0) {
				// 为了记录一个选取数组,从而回溯 dp 路径
                choice[i][j] = true;
				// 由于权值和体积是相同值,所以只用 w 数组一维记录即可
                dp[j] = max(dp[j], dp[j - w[i - 1]] + w[i - 1]);
            }
        }
    }

    vector<int> aa;
    dfs(V, aa);
    return 0;
}

// 404 404 251 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31
// 404 404 404 404 404
// 404 500 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31
// 404 965 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31
// 404 996 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31
// 404 1024 251 31 31 31 31 31 31 31 31 31 31 31
// 500 404 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31
// 500 1024 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31
// 965 404 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31
// 965 1024 31
// 996 404 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31
// 996 1024
// 1024 404 251 31 31 31 31 31 31 31 31 31 31 31
// 1024 500 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31
// 1024 965 31
// 1024 996

更多关于背包问题的分类,可以看看背包九讲这个教程,点击查看原文可以看到。

根据结果来解释一下 2020

当然除了 404 404 404 404 4041024 996 这两个组合,我们也可以使用其他组合来解释 2020。例如:

  1. 1024 + 965 + 31 :(乐观的) 每个月都是开心的 965
  2. 404 * 2 + 31 * 31 + 251 :(尴尬的)月复一月的出现 404,就会被 251
  3. 500 + 31 * 16 + 1024:(忧伤的)每个月都会出现 500

解释的方法有很多,所以希望大家也可以以平常心来面对即将到来的 2020,不要过于悲观和消极。当然,也祝愿大家在 2020 里身体健康!