Simplified knapsack in PHP

Question

I have two instances where I'd like to display information in a "justified" alignment - but I don't care if the values are switched in order. One example being displaying the usernames of people online:

Anton Brother68 Commissar Dougheater Elflord Foobar Goop Hoo Iee Joo

Rearranging them we could get exactly 22 characters long on each line:

Anton Brother68 Foobar
Commissar Elflord Goop
Dougheater Hoo Iee Joo

This is kind of a knapsack, except seems like there ought to be a P solution since I don't care about perfection, and I have multiple lines.

Second instance is identical, except instead of names and character count I would be displaying random images and use their width.

I'm doing it in PHP, though i'm just looking for the algorithm — Mikhail, Jul 07 '11 at 15:26
How many spaces do you want to allow between the strings? Do you want the minimum number of spaces or is any number of spaces allowed? — rjzii, Jul 07 '11 at 15:28
Well i'm displaying it on the web, so all spaces will become 1. — Mikhail, Jul 07 '11 at 15:37
Well, you're displaying it on the web, so you can use CSS to change the presentation in arbitrary ways. — Rein Henrichs, Jul 07 '11 at 17:24
Besides which, you can actually change the way whitespace is handled with CSS, so spaces will not necessarily become one. — Rein Henrichs, Jul 07 '11 at 17:24
I can also use non breakable spaces. I don't think this is a crucial point within this question — Mikhail, Jul 07 '11 at 17:54
Ok, but what you describe is not always possible, so what are you aiming for? Lines with equal width? Fixed number of lines? Or you want just to test if it is possible to arrange those names as in your example? — Gabriel Ščerbák, Jul 10 '11 at 21:47
You need to fully specify the parameters of the problem. Are the parameters: total length of the text; the number of words; the length of each word; the number of lines; the number of characters per line? Are these all parameters? — stackoverflowuser2010, Nov 14 '11 at 19:42

score 1 · Answer 1 · answered Aug 16 '11 at 15:19

1

It doesn't feel like a knapsack problem because the utlity of all words placed is 1 (correct me if I'm wrong).

Perhaps binpacking instead?

answered Aug 16 '11 at 15:19

Jonno

1,738
10
17

Utility would be the length. You just have more than one sack :) – Mikhail Aug 16 '11 at 23:58
Then what is the cost? If they all have the same utility or cost, it still doesn't feel knapsack – Jonno Aug 18 '11 at 21:05
cost is also the length. They don't have same utility or cost across the items because "Joe" is 3, and "Mikhail" is 7 – Mikhail Aug 23 '11 at 14:01

score 1 · Accepted Answer · answered Dec 14 '11 at 18:10

Decide the number of lines, for example by taking the total length and dividing by some maximum line size. Sort the list of names by descending length. Repeatedly take the longest name off the sorted list and add it to the shortest line so far. After you have added all names to the lines, you may want to randomize the order or sort alphabetically within the lines to make it look better.

This is a very close approximation of the optimum solution.

Simplified knapsack in PHP

2 Answers2