Geek asks and answers

Splitting an array into halves with equal sums of P or NP?

It was an interview question with an algorithm about a partition problem.

You are given an array that consists of numbers from 0 to 5 digits. Write a function that returns whether the array can be divided into two halves, such that the sum of the two halves will be equal.

Is this an NP problem or can it be solved with dynamic programming?

"between 0 and 5 digits" means 0 ~ 99999, I think.

I found a good answer to this external SO here .

+3
source share
5 answers

I. The problem is NP, and I am sure that it can be solved in pseudopolynomial time with dynamic programming.

http://en.wikipedia.org/wiki/Partition_problem

NP- - .

0-5 , , NP-. 0- ?

, , . " 2 ", , "" .

, , , , DP, . - , , ", , , DP, ".

+1

, , NP - .

NP-, ( 0 5 ).

, " ", m/n < 1

+3

, , , . .

, , ? NP-Complete (. http://en.wikipedia.org/wiki/Partition_problem ), , , ( ).

NP-Complete, , ? ? , , ?

, , inteviewer.

: ( 100000, , ) . http://en.wikipedia.org/wiki/Knapsack_problem Knapsack.

+2

, , .

bin.

wikipage Partition_Problem, , , Subset_Sum_Problem, . wiki

0

You can adapt this algorithm to the partition problem, it does not require many changes.

Linear Algorithm to Solve a Subset of Sum NP-Complete Problem pure Python Implementation

https://github.com/maxtuno/Universal/blob/master/linear_sum_subset_algorithm_oscar_riveros.py

#!/usr/bin/env python3

__author__ = "O. A. Riveros"
__copyright__ = "Copyright 2014, O. A. Riveros, All right reserved"
__license__ = "MIT"
__email__ = "oscar.riveros@gmail.com"

"""
O. A. Riveros
http://independent.academia.edu/oarr
http://twitter.com/maxtuno
"""

"""
first 100 primes
"""
data = [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199,211,223,227,229,233,239,241,251,257,263,269,271,277,281,283,293,307,311,313,317,331,337,347,349,353,359,367,373,379,383,389,397,401,409,419,421,431,433,439,443,449,457,461,463,467,479,487,491,499,503,509,521,523,541]

solution = [1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1]

"""
for custom entertainment
solution = [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
"""

target = sum([data[i] for i in range(len(solution)) if solution[i] == 1])

l = len(data)

size = len('{0:b}'.format(sum(data)))

def rotate(l,n):
    return l[n:] + l[:n]

def slice(l, n):
    return list(int(l[i:i+n], 2) for i in range(0, len(l), n))

data_second_order = []
for i in range(l):
    data_second_order += rotate(data, i)

T = 0
for i in range(l):
    T += int(''.join('{0:b}'.format(k).zfill(size) for k in rotate(data_second_order, i)), 2)
    t = slice('{0:b}'.format(T).zfill(size*(l**2)), size)
    if (target in t):
        '''
        for review the results
        print('The target {} found in {} steps from {}.'.format(target, i + 1, t))
        '''
        print('The target {} found in {} steps'.format(target, i + 1))
        break

"""
The target 24133 found in 100 steps
"""
0
source

More articles:


All Articles