2017 Tokyo Westerns CTF 3rd Backpacker's Problem¶
A cpp file is given in the title, which probably means the following
Given the integers a_1, a_2, ..., a_N, your task is to find a subsequence b of a where b_1 + b_2 + ... + b_K = 0. Input Format: N a_1 a_2 ... a_N Answer Format: K b_1 b_2 ... b_K Example Input: 4 -8 -2 3 5 Example Answer: 3 -8 3 5
It is a backpack problem. Among them, in this question, we need to solve 20 such backpack problems, the size of the backpack is 1 * 10 ~ 20 * 10 in order. The backpack problem of subset summation is an NPC problem, and the time complexity of the problem increases exponentially with the size of the backpack. The size of the backpack here is at most 200, and it is obviously impossible to use brute force.
To be completed
本页面的全部内容在 CC BY-NC-SA 4.0 协议之条款下提供，附加条款亦可能应用。