题目说明

问题：已知一背包加密的公钥为{615436700291,415460700271,15508700231,846430100773,677471501215, 139578302079,179168604148,789306608798,563224517265,364498233536,229056467022,670323428329, 115934481316,44989786476,518624653302,149955258190,728568829281,796899516776,546782575075, 178164449829,356328899658,712657799316,569303048254,223205396187,446410792374,892821584748, 524144817108,132888933895,611875519857,877653387647,839906074973,35774353074}，密文为6020587936087，试求明文二进制表示（形如：01001010000001110101001100001110）。真正的背包加密要复杂得多，而且有固定的解法。这个是我们就题论题，首先我们这个问题是面向用例编程，和OJ不太一样，我们是用方法来解决这一个特殊问题。先做预处理，并初始化long long数组a

#include<iostream>
#include<vector>
#define WEIGHT 6020587936087
using namespace std;
typedef long long ll;

int n;

思考

首先看到“背包”两字就非常敏感，妥妥的动态规划，而且有且仅有一个解满足条件，天哪，这不正好。我想是不是这么个情况。这是一个存在性背包问题，我们可以通过两重循环在\(\large O \normalsize \left( n \times MAX\right)\)的时间内完成，并且我们可以找一个pre数组来记录前一个取值，很轻松地找到那组可行解，好耶，这种做法相当研究生。那么我们思考一下写出动态规划的代码。

动态规划

vector<ll> a = { 615436700291,415460700271,15508700231,846430100773,677471501215,139578302079,179168604148,789306608798,563224517265,364498233536,229056467022,670323428329,115934481316,44989786476,518624653302,149955258190,728568829281,796899516776,546782575075,178164449829,356328899658,712657799316,569303048254,223205396187,446410792374,892821584748,524144817108,132888933895,611875519857,877653387647,839906074973,35774353074 };
int size = a.size(); //确定物品数量
bool* dp = new bool[WEIGHT + 1]; //dp数组下标意义为重量
unordered_map<ll, pair<ll, int>> premp; //使用哈希表求沿途的元素，对应映射为：该重量对应前一重量和填入背包的元素
for (int j = 0; j < size; ++j) //由于物品只能使用一次，外层遍历物品，内层遍历重量
	for (ll i = 0; i < WEIGHT; ++i)
		if ((i == a[j]) || (i >= a[j] && dp[i - a[j]] == true)) //使得i能被拼出的条件：直接有对应的物品，或(i - 某一物品重量)能被拼出
		{
			dp[i] = true;
			premp[i].first = a[j];
			premp[i].second = j; //确定倒序查找的线索
		}
vector<bool> taken(size, 0);
int j = 0;
for (ll i = WEIGHT; i == premp[i].second; i = premp[i].first, j = premp[i].second) //倒序寻找加入背包的元素
	taken[j] = true;
taken[j] = true;
for (int i = 0; i < size; ++i) //输出01序列
	cout << taken[i];
cout << endl;

当我们迫不及待的按下F5的时候会发现报错了，啊这为啥会有这么大的数组，我们看到WEIGHT是一个让人震惊的数字。你可能会说，我们干脆从\(\mathop{min}\limits_{i \in \left[0 , 31\right]}\left\{ a_{i} \right\}\)开始找，但是依然是一个很大的数字，诶，这个题动态规划失效了。当然还有其他的方法优化处理，楼主菜鸡表示不会。

搜索

对问题进行转化，实际上这是一个求子集合的问题，即找到某一集合，使得各元素和等于所给值sum，并指明该集合。而且我们注意这道题数组的大小为32，对于任何一个元素，拿与不拿是两种情况可分别搜索，比照嗯二叉搜索的时间复杂度\(\large O \normalsize \left(2^{n}\right)\)，我们嗯穷举的量大概是\(2^{32}\)，也就是\(10^{10}\)，这个量还是非常猛，但是至少可以让程序run起来。顺着这个思路我们先稍微写一下朴素的搜索算法，大概像这样。

void backtracking(int cur, ll sum, vector<bool> istaken, vector<ll> a)
{
	if (cur == n - 1)
	{
		if (sum == WEIGHT)
		{
			for (int i = 0; i < n; ++i)
				cout << istaken[i];
			cout << endl;
		}
		return;
	}

	istaken[cur] = true;
	backtracking(cur + 1, sum + a[cur], istaken, a);
	istaken[cur] = false;
	backtracking(cur + 1, sum, istaken, a);
}

我们注意到搜索的终极大法是剪枝，有枝可以剪吗，答案是肯定的，一旦我们当前和已经超过了最大可容纳重量WEIGHT，那又没有负数，肯定要把背包撑爆，不会成为我们的最终选择，那我们干脆直接吧这种给淘汰掉。而且我们不难看出这个剪枝能使得效率提高很多。

#include<iostream>
#include<vector>
#define WEIGHT 6020587936087
	using namespace std;
	typedef long long ll;

	int n;

	/*
	函数名: backtracking
	参数说明:
	int cur : 表明当前递归层次，即当前考虑到数组中第cur + 1个元素
	long long sum : 进入函数时的当前和
	vector<bool> istaken : 记录加入背包的元素
	vector<long long> a : 物品重量数组
	int n : 全局变量，表明物品总量
	返回值: 无(隐含全局变量操作)
	*/

	void backtracking(int cur, ll sum, vector<bool> istaken, vector<ll> a)
	{
		if (cur == n - 1) //递归到最后一个物品时判断后回溯
		{
			if (sum == WEIGHT) //若能拼出WEIGHT，输出信息，也可以利用全局变量返回
			{
				for (int i = 0; i < n; ++i)
					cout << istaken[i];
				cout << endl;
			}
			return;
		}

		if (sum + a[cur] <= WEIGHT) //剪枝操作，若加入当前元素后重量已经超过WEIGHT，后面已经不可能拼出WEIGHT，不再向下递归
		{
			istaken[cur] = true; //先加入istaken
			backtracking(cur + 1, sum + a[cur], istaken, a); //从cur + 1开始，以sum + a[cur]为当前和，向下搜索
			istaken[cur] = false; //状态还原
		}
		if (sum <= WEIGHT) //剪枝操作，若当前重量超过WEIGHT，后面已经不可能拼出WEIGHT，不再向下递归
		{
			istaken[cur] = false; //纯属对应操作，可有可无
			backtracking(cur + 1, sum, istaken, a); //从cur + 1开始，以sum为当前和，向下搜索
		}
	}

	int main()
	{
		vector<ll> a = { 615436700291,415460700271,15508700231,846430100773,677471501215,139578302079,179168604148,789306608798,563224517265,364498233536,229056467022,670323428329,115934481316,44989786476,518624653302,149955258190,728568829281,796899516776,546782575075,178164449829,356328899658,712657799316,569303048254,223205396187,446410792374,892821584748,524144817108,132888933895,611875519857,877653387647,839906074973,35774353074 };
		n = a.size();
		vector<bool> istaken(n, 0);
		backtracking(0, 0, istaken, a); //注意开始搜索的条件

		return 0;
	}