0
$\begingroup$

So I am studying for my Algorithm theory exam and this is the problem i could not solve:

Given numbers $x_1, x_2, ..., x_n$ which are the sizes of $n$ files and disk capacity $D$. Determine if you can seperate these files into $3$ disks so that, in every disk sum of doesn't exceed $D$. Justify that this problem belongs to class NP

So i am thinking you can seperate only if:
$x_i < D$ and if $x_1 + x_2 + ... + x_n > 3\cdot D$
Are these the only rules?

$\endgroup$
1
0
$\begingroup$

Nobody asked you to give conditions on when that happens. Also, your second condition is incorrect: if all $x_1,...,x_n$ are 0 then for any $D$ there is a solution.

What you are asked is to show this is in NP, hence, show a "prover-verifyer" solution:

The proof will be the following: for each $1\le i\le n$, the proof at index $i$, is $p_i$ and will be one of three numbers ($1,2,3$ for example) that will indicate in which disk we want to put the file $x_i$. Then, just check that for every one of the three disks, the sum of the $x$'s in it do not exceed $D$.

Its not hard to show why this algorithm is correct, so I will leave it for you to try on your own.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.