| I suspect the problem is known to be NP-complete. However, there probably
are no more than 30 songs, so the problem should be tractable. Try the
following Pascal program.
program songs (input, output);
const
k_songs = 20;
type
slength = integer; { or: real }
var
closest, ctot, stot, stot2 : slength;
ss : integer; { Number of songs }
s : array [1..k_songs] of slength; { Lengths of songs }
u : array [0..k_songs] of slength; { Sum of lengths of songs }
t : array [1..k_songs] of boolean; { Which songs on this side }
function half (x: slength) : slength;
begin
half := x div 2; { or: x / 2 }
end;
procedure readsongs;
begin
writeln ('Enter the song lengths, with a zero to terminate the list');
ss := 1;
read (s[ss]);
while (s[ss] > 0) and (ss < k_songs) do
begin
ss := ss + 1;
read (s[ss]);
end;
readln;
ss := ss - 1;
end;
procedure calc_stot;
var
i : integer;
begin
stot := 0;
for i := 1 to ss do stot := stot + s[i];
stot2 := half(stot);
u[0] := 0;
for i := 1 to ss do u[i] := u[i-1] + s[i];
for i := 1 to ss do t[i] := false;
end;
procedure new_closest;
var
others : boolean;
i : integer;
begin
closest := ctot;
write ('New closest: ',closest : 0,' = ');
others := false;
for i := 1 to ss do if t[i] then
begin
if others then write (' + ');
others := true;
write (s[i] : 0);
end;
writeln;
write (' ',stot-closest : 0,' = ');
others := false;
for i := 1 to ss do if not t[i] then
begin
if others then write (' + ');
others := true;
write (s[i] : 0);
end;
writeln;
writeln;
end;
procedure recur (ns: integer);
begin
if ns > 0 then
begin
if ctot + u[ns] > closest then { or: >= }
begin
ctot := ctot + s[ns]; t[ns] := true;
if ctot <= stot2 then recur (ns-1);
ctot := ctot - s[ns]; t[ns] := false;
recur (ns-1);
end
end
else
begin
if ctot > closest then new_closest; { or: ctot >= closest }
end;
end;
begin
readsongs;
while ss > 0 do
begin
calc_stot;
closest := 0;
ctot := 0;
recur (ss);
readsongs;
end;
end.
|
| >> It means it can be solved in polynomial time if one can guess the
>> correct strategy to follow.
Or better, that in time at most a polynomial function of
the size of an instance of the problem, you can both
write down an answer (nondeterministically) and verify
that it is indeed correct.
For example, to show that a k bit number N is
composite, you can nondeterministically write down two
factors (greater than one) and then verify the
compositeness by multiplying them out to get N, all in
time a polynomial function of k (not of N). So
"compositeness" is in NP.
Dan
|
| First some minor vocabulary technicalities:
The classes NP and NP-complete are classes of *decision* problems,
i.e., problems which can be answered with a simple yes or no. A
problem, whether or not it is a decision problem, which is "at least
as hard as" an NP-complete problem (i.e., for which a polynomial time
solution would imply a polynomial solution for the NP-complete problem)
is known as NP-hard. Most (all?) of the NP-complete problems are
associated with an NP-hard optimization problem, which is sometimes
loosely referred to as being NP-complete.
For example the Traveling Salesman *Optimization* problem is: given a
set of cities and the distances between each, determine the minimum
length path connecting all the cities. This problem is NP-*hard*
rather than NP-complete. The Traveling Salesman *Decision* problem is:
given a set of cities and the distances between each determine if there
is a least one path connecting all the cities whose length is less than
a given length. This problem is NP-*complete*.
Anyway...
The problem in .0 is easily shown to be NP-hard, since the NP-hard
problem associated with one of the classic NP-complete problems is a
special case of this one. The problem is known in the literature
as PARTITION, and it is one of the most frequently used for
demonstrating the NP-completeness of new problems.
PARTITION -- given a set of integer values, can the set be partitioned
into two distinct sets such that the sums of the values in each set
are equal?
It's easy to see that a polynomial time solution to the problem in
.0 would provide a polynomial time solution to this decision problem:
take each integer in the set and cast it as (real) playing time. If
the solution comes out to the two sides being equal than the answer
to the partition problem is YES otherwise it is NO.
PARTITION is particularly interesting because it is the primary example
of a class of problems known as pseudo-polynomial. This means that
although this problem is NP-complete in the primary measure of size (in
this case the number of elements in the set), there is a known
polynomial time solution in some other quantity (in this case, the
sum of the values in the set). If n is the number of elements in the
set and S is the size of the sum of the values in the set, then
dynamic programming provides a solution of O(nS) time and O(S) space.
Two reasonable assumptions about the relationship between n and S:
1) The maximum size is independent of the number of elements (e.g.,
the elements "chop up" a fixed or randomly chosen size total
into n pieces). In this case dynamic programming provides a
solution which is linear in the number of elements.
2) The maximum size is linear in the number of elements (e.g., the
average size of each element does not depend on the number of
elements). In this case dynamic programming provides a solution
which is quadratic in the number of elements.
The reason that this does prove that P=NP is that the original problem
statement does not rule out the possibility of the total size
increasing exponentially or even superexponentially with the number of
elements. For example, if the set were built up by adding elements
such that the i'th element is chosen to be in the range 0 to 2^i, then
the maximum sum of the elements would increase exponentially with
the number of elements.
The method cannot be applied directly to the problem in .0 (at least as
far as I can tell), since it depends on the "playing times" of each
piece being an integer. It can be used to produce a very good
approximation to the optimal solution, however, by dividing the total
playing time into enough integral time-units and rounding each real
valued playing time to the appropriate integer value.
Note that even if you *express* your playing times as integers, the
playing times are actually real values in the "real world". In that
case, however, the solution in .1 is also an approximation. (Yes,
of course, any transcription for solution will involve rounding to some
minimum measurable unit, but as that unit becomes smaller, the value of
"S" becomes larger and the dynamic programming solution becomes less
practical, while the complete enumeration method is unaffected by the
increasing accuracy). If your playing times are expressed as integers,
then the dynamic programming solution will produce a minimum result.
The program in .1 contains a subtle error when used with REAL values.
The when a playing time is added and then subtracted from "ctot" in
recur, rounding errors can result in the final value of ctot being
slightly different from its initial value. Over millions of iterations
this small difference can result in a substantial error. A local
variable should be used to save and restore ctot.
I submitted batch files containing the following a) Nothing, b) The
enumeration method in .1 with 32 elements, with the above correction
and modified to only print out the final solution, and c) The dynamic
programming method with 32 elements, printing out the final solution as
in b.
The "charged CPU time" for a) was 0.81 seconds for b) was 1 hour 13
minutes and 44.14 seconds and for c) was 1.79 seconds.
The data used for b) and c) was the same 32 uniform pseudo-random
values in the range 0.0 to 1.0. The expected length of a song was
therefore .5. The ideal time per side (half the total playing time)
was 8.15385437. The dynamic programming approximation, dividing the
total playing time into 20000 integral units, gave a value differing
from this by .000545501709 (roughly half the width of the time unit:
note that this is typical but not guaranteed). The complete
enumeration managed to find a perfect split (within the accuracy of
the single precision arithmetic used).
Topher
program songs (input, output);
const
k_songs = 32; { Maximum number of songs allowed. }
max_play = 20000; { Maximum total playing time (in pseudo-time
units). }
half_max_play = max_play div 2;
{ Playing time (in pseudo-time units) of one
side. }
f_max_play = 20000.0; { Max_play as a real number. }
type
slength = real;
var
closest, stot, stot2 : slength;
ss : integer; { Number of songs }
s : array [1..k_songs] of slength; { Lengths of songs }
t : array [1..k_songs] of boolean; { Which songs on this side }
int_s : array [1..k_songs] of integer;
{ Lengths of songs rounded to integral
pseudo-time units. }
times : array [0..half_max_play] of integer;
{ Possible times of some play
combo. -1 means no combo for
that amount of time found yet.
1..k_songs means combo exists
with that value as the largest
song index. 0 (found only at
index location 0) means play time
of the empty combo. }
function half (x: slength) : slength;
begin
half := x / 2;
end;
procedure readsongs;
begin
writeln ('Enter the song lengths, with a zero to terminate the list');
ss := 1;
read (s[ss]);
while (s[ss] > 0) and (ss < k_songs) do
begin
ss := ss + 1;
read (s[ss]);
end;
readln;
ss := ss - 1;
end;
procedure calc_stot;
var
i : integer;
begin
stot := 0;
for i := 1 to ss do stot := stot + s[i];
stot2 := half(stot);
for i := 1 to ss do t[i] := false;
end;
procedure show_closest;
var
others : boolean;
i : integer;
begin
write ('Closest: ',closest : 0,' = ');
others := false;
for i := 1 to ss do if t[i] then
begin
if others then write (' + ');
others := true;
write (s[i] : 0);
end;
writeln;
write (' ',stot-closest : 0,' = ');
others := false;
for i := 1 to ss do if not t[i] then
begin
if others then write (' + ');
others := true;
write (s[i] : 0);
end;
writeln;
writeln;
end;
procedure init;
var
i : integer;
begin
{ Round each element of s into an appropriate integral pseudo-unit and
place in int_s. }
for i := 1 to ss do
int_s[i] := ROUND((s[i]*f_max_play)/stot);
{ Initially all combos are unobtained except the empty combo. }
for i := 1 to half_max_play do times[i] := -1;
times[0] := 0;
end;
procedure find_closest;
var
spnt : integer; { Pointer into s and int_s arrays. }
play_time : integer; { Holds the playing time of a song. }
time_pnt : integer; { Pointer into the times array. }
new_time : integer; { Newly found total playing time. }
begin
{ For each song ... }
for spnt := 1 to ss do
begin
{ ... Add its play time to each existing combo which will not
result in the new combo exceeding 1/2 the total playing time
and record it if there is not a combo which already results
in that playing time. }
play_time := int_s[spnt];
for time_pnt := half_max_play - play_time downto 0 do
if times[time_pnt] >= 0
then
begin
new_time := time_pnt + play_time;
if times[new_time] < 0
then
times[new_time] := spnt;
end;
end;
{ Scan down for the combo playing time closest to half the total
playing time. }
time_pnt := half_max_play;
while (times[time_pnt] < 0) do
time_pnt := time_pnt - 1;
closest := 0.0;
spnt := times[time_pnt];
while (spnt > 0) do
begin
{ Times[time_pnt] contains the maximum index of the songs in the
current combo being examined. To find the next index, subtract
that songs playing time from the current playing-time and the
result will be the playing time of the combo on which this one
was built. }
t[spnt] := true;
closest := closest + s[spnt];
time_pnt := time_pnt - int_s[spnt];
spnt := times[time_pnt];
end;
end;
begin
readsongs;
while ss > 0 do
begin
calc_stot;
init;
find_closest;
show_closest;
readsongs;
end;
end.
|