Knapsack Cryptosystem(折半搜索)_eazo的博客-程序员宅基地

技术标签: 搜索  

题目描述
Amy asks Mr. B problem D. Please help Mr. B to solve the following problem.

Amy wants to crack Merkle–Hellman knapsack cryptosystem. Please help it.

Given an array {ai} with length n, and the sum s.
Please find a subset of {ai}, such that the sum of the subset is s.

For more details about Merkle–Hellman knapsack cryptosystem Please read
https://en.wikipedia.org/wiki/Merkle%E2%80%93Hellman_knapsack_cryptosystem
https://blog.nowcoder.net/n/66ec16042de7421ea87619a72683f807
Because of some reason, you might not be able to open Wikipedia.
Whether you read it or not, this problem is solvable.

输入描述:
The first line contains two integers, which are n(1 <= n <= 36) and s(0 <= s < 9 * 1018)
The second line contains n integers, which are {ai}(0 < ai < 2 * 1017).

{ai} is generated like in the Merkle–Hellman knapsack cryptosystem, so there exists a solution and the solution is unique.
Also, according to the algorithm, for any subset sum s, if there exists a solution, then the solution is unique.

输出描述:
Output a 01 sequence.

If the i-th digit is 1, then ai is in the subset.
If the i-th digit is 0, then ai is not in the subset.

示例1
输入
8 1129
295 592 301 14 28 353 120 236

输出
01100001

说明
This is the example in Wikipedia.

示例2
输入
36 68719476735
1 2 4 8 16 32 64 128 256 512 1024 2048 4096 8192 16384 32768 65536 131072 262144 524288 1048576 2097152 4194304 8388608 16777216 33554432 67108864 134217728 268435456 536870912 1073741824 2147483648 4294967296 8589934592 17179869184 34359738368

输出
111111111111111111111111111111111111

思路
折半搜索,将搜索分为两段进行

代码实现

#include <bits/stdc++.h>

using namespace std;
typedef pair<int,int> P;
typedef long long ll;
const int N=50;
const int INF=0x3f3f3f;
const ll mod=1e9;

ll s,a[N];
int n;
map<ll,int>ma;


int main()
{
    scanf("%d%lld",&n,&s);
    for(int i=0;i<n;i++)
    {
        scanf("%lld",&a[i]);
    }
    int mid=n>>1;
    for(int i=0;i<(1<<mid);i++)
    {
        ll sum=0;
        for(int j=0;j<mid;j++)
        {
            if((i>>j)&1)
            {
                sum+=a[j];
            }
        }
        ma[sum]=i;
    }
    int nmid=n-mid;
    for(int i=0;i<(1<<nmid);i++)
    {
        ll sum=0;
        for(int j=0;j<nmid;j++)
        {
            if((i>>j)&1)
            {
                sum+=a[j+mid];
            }
        }
        if(ma[s-sum])
        {
            int t=ma[s-sum];
            for(int j=0;j<mid;j++) printf("%d",(t>>j)&1);
            for(int j=0;j<nmid;j++) printf("%d",(i>>j)&1);
            puts("");
            break;
        }
    }
    return 0;
}


版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/weixin_43935894/article/details/99655281

智能推荐

pycharm安装教程,2021.11月社区版安装_508小怪兽的博客-程序员宅基地_pycharm社区版安装包

第一步安装解释器,第二步安装pycharm1第一步安装解释器1.1什么是解释器:?? 就是将Python程序翻译成为计算机可以识别的01代码1.2安装解释器:解释器安装地址:https://www.python.org/downloads/release/python-372根据自己的操作系统安装适配的解释器: 这里以Windows为例注意安装的时候我们需要需注意吧解释器添加到环境变量里面双击开始安装勾选add python to path ,如果安装的时候没有勾选,请安装结束以后按

Base64编码与解码_小明同学爱思考-程序员宅基地

Base64原理Base64是一种用64个字符来表示任意二进制数据的方法。对于二进制数据,每3个字节一组,编码为4个字节,即3×8bit=4×6bit。如下图,将连续的3个字节(8bit)分为4个6bit,然后将每个6bit高两位全补0,分别组成1字节(8bit),根据每个字节的数字查表的到对应的字符,进而得到编码后的字符串。 当原来二进制数据的字节数不是3的倍数时,可以在追加补1个或...

linux显示变量命令,Linux中显示shell变量的几种命令区别_逆光的温暖的博客-程序员宅基地

Linux中显示shell变量的几种命令区别shell变量包括两种变量1.本shell私有的变量:通过赋值语句定义好的变量,可以通过如下方法定义shell变量A1="1234"delcare A2="2345"2.用户的环境变量:通过export语法导出的shell私有变量,可以通过如下方法导出用户环境变量A1="1234"export A1 #先定义再导出export A3="34"导出成的用...

synchronized的四种用法_augfun的博客-程序员宅基地

一 修饰方法Synchronized修饰一个方法很简单,就是在方法的前面加synchronized,synchronized修饰方法和修饰一个代码块类似,只是作用范围不一样,修饰代码块是大括号括起来的范围,而修饰方法范围是整个函数。例如:方法一public synchronized void method(){ // todo}方法二public void ...

C++的Vector用法_track sun的博客-程序员宅基地

转自:http://www.cnblogs.com/wang7/archive/2012/04/27/2474138.html在c++中,vector是一个十分有用的容器,下面对这个容器做一下总结。1 基本操作(1)头文件#include&lt;vector&gt;.(2)创建vector对象,vector&lt;int&gt; vec;(3)尾部插入数字:vec.push_b...

oracle 挂载不上data,AnyBackup-CDM Oracle单机挂载恢复失败,提示错误信息:挂载失败,原因:指定的挂载点不为空,请指定一个空的文件夹作为挂载点..._被烤焦的羊的博客-程序员宅基地

关键字挂载点不为空适用产品AnyBackup CDM7.0.1-7.0.8问题描述在 AnyBackup 数据访问界面,新建 Oracle 副本数据管理挂载恢复任务,任务执行失败,执行输出有如下错误信息:挂载失败,原因:指定的挂载点不为空,请指定一个空的文件夹作为挂载点。问题影响AnyBackup CDM Oracle 挂载恢复失败。问题原因选择的数据卷或日志卷的挂载目录是非空目录。解决方案为...

随便推点

药品盘点机,药店盘点机,无线移动智能终端条码解决方案实现药店仓储管理信息化_汉码盘点机PDA-程序员宅基地

新版的GSP实施以来,对医药行业的信息化发展提出了更高的要求,要求企业全面通过计算机管理来全面强化药店的经营和管理。现在有一定规模的医药企业均会上一套医药进销存管理软件ERP对药品的流通等信息进行管理,但是随着药店规模的不断发展,药品种类越来越多,药品数量也越来越多,工作人员在流程过程中手工录入到进销存管理软件ERP中的数据也越来越多。而且这些数据大量手工录入,工作量大,而且容易出错。这些错误日积

element-icons.ttf 与 element-icons.woff 本地图标乱码_星河之砂的博客-程序员宅基地

一、现象使用http资源路径正常,下载下来之后异常,浪费不少时间,Failed to decode downloaded font: file:///D:/foreseeworkz/workplacesszzc/SpringMvcDemo2/SpringMvcDemo2/src/main/webapp/quarzt/fonts/element-icons.ttf?t=1510834658947JobManager.html:1 OTS parsing error: invalid versio

HDU-2509-Be the Winner(尼姆博弈)_Herod_的博客-程序员宅基地

Be the WinnerProblem DescriptionLet’s consider m apples divided into n groups. Each group contains no more than 100 apples, arranged in a line. You can take any number of consecutive apples at one t...

计算机网络批量确认,【02-计算机网络面试核心】01-tcp协议与三次握手/四次挥手..._咪马3213�m~~的博客-程序员宅基地

1.tcp协议报文tcp协议报文如下: 源端口号:报文发起方的端口号目的端口号: 报文接收方的端口号序号:报文序列确认序号:期望收到对方下一个字节的序号首部长度:tcp数据距离tcp起始处有多远保留:留待今后使用tcp标记位:URG:紧急指针标志,为1时紧急指针域有效,为0时则忽略ACK:确认号标志,为1时确认号有效,为0时表示报文中不含确认信息,忽略确认号字段PSH:push标志,接收方接收到报...

tcp协议用来提供什么服务器,关于TCP协议,我想你应该懂了!_深渊号角�mkq0.~的博客-程序员宅基地

TCP是什么?程序员TCP(Transmission Control Protocol 传输控制协议)是一种面向链接(链接导向)的、可靠的、 基于IP的传输层协议。TCP在IP报文的协议号是6。TCP是一个超级麻烦的协议,而它又是互联网的基础,也是每一个程序员必备的基本功。首先来看看OSI的七层模型:面试 咱们须要知道TCP工做在网络OSI的七层模型中的第四层——Transport层,IP在第三层...

Vue-Vue列表渲染v-for_panfuyong11的专栏-程序员宅基地

一、v-for 循环数组HTML代码&lt;div id="app"&gt; &lt;ul&gt; &lt;li v-for='item in list'&gt;{{item}}&lt;/li&gt; &lt;/ul&gt;&lt;/div&gt;JS代码new Vue({ el:'#app', data:{ ...

推荐文章

热门文章

相关标签