Question

Consider the following 3-PARTITION problem. Given integers${\mathrm{a}}_1,...,{\mathrm{a}}_{\mathrm{n}},$ we want to determine whether it is possible to partition of $\left\{1,...,n\right\}$ into three disjoint subsets $\mathbf{I}\mathbf{,}\mathbf{J}\mathbf{,}\mathbf{K}$such that

$\underset{i\in I}{\sum a_i}=\underset{j\in J}{\sum a_j}=\underset{k\in k}{\sum a_k}=\frac{1}{3}\underset{i\in 1}{\sum a_i}$ .

For example, for input$\left(1,2,3,4,4,5,8\right)$ the answer is yes, because there is the partition$\left(1,8\right)\mathbf{,}\left(4,5\right)\mathbf{,}\left(2,3,4\right)\mathbf{.}$ On the other hand, for input$\left(2,2,3,5\right)$ the answer is no. Devise and analyze a dynamic programming algorithm$\mathbf{3}\mathbf{-}\mathbf{PARTITION}$ for that runs in time polynomial in n and in ${\mathbf{\Sigma }}_{\mathbf{i}}{\mathbf{a}}_{\mathbf{i}}\mathbf{.}$

Short answer

Use dynamic programming to perform $3-\mathrm{PARTITION}$

Step-by-step solution

Dynamic programming approach

In dynamic programming there are all possibilities and more time as compared to greedy programming. and the Dynamic programming approach always gives the accurate or correct answer. In dynamic programming have to compute only distinct function call because as soon as compute and store in one data structure so that after this reuse afterward if it is needed.

Defining the Recurrence Relation and algorithm

Let us assume we have two backpacks and we are filling both of them at same time and whatever is leftover will be filled in third backpack.

Now we will pick an item and see if it fits to first or second backpacks.

Let us assume,

$W={\sum }_{(i=1)}^n\sum a_i$

Now at the end, we will check that if we have W/3, W/3 in both backpacks. This will ensure us that we have W/3 in third backpack. Herefor input$\left(1,2,3,4,4,5,8\right)$ the answer is yes, because there is the partition$\left(1,8\right),\left(4,5\right),\left(2,3,4\right).$Dynamic programming approach always gives the accurate or correct answer. In dynamic programming have to compute only distinct function call because as soon as compute and store in one data structure so that after this reuse afterward if it is needed.

On the other hand, for input the answer is a dynamic programming algorithm for$3-PARTITION.$ that runs in time polynomial in n and in${\Sigma }_i{a}_i.$

First let us define the initial condition:

Base case will be,

$P\left[x,y,0\right]=0andP\left[0,0,0\right]=1$

Recurrence Relation is:

,

For the case,

$P\left[x,y,0\right]=0andP\left[0,0,0\right]=1$

And, the value defined as,

$W={\sum }_{(i=1)}^n\sum a_i$

in time polynomial inn,

${\Sigma }_i{a}_i.$

Thus, Subproblem is:

$p\left[x,y,i-1\right]=\left\{1;forx=y=i=0\right\}$

$p\left[x,y,i\right]=p\left[x,y,i-1\right]\cup p\left[x-a,y,i-1\right]\cup p\left[x,y-a,i-1\right];fori,x,y>0$

Here, as let’s fill two backpacks in$\frac{w}{3}$ runtime, and we are partitioning for some integers, our time complexity becomes$O\left(n*W^2\right).$ This is the desired time complexity.