It once cropped up for seemingly simple everyday problem that I will describe here:
When I was still a graduate student (1980's), I was helping out some local businesses. There was a need to print a lot of receipts, and these receipts would be of some size, measured in number of lines. Say 10, 35, 20, 5, 12 etc. The paper size would be about 60 lines.
And then, we thought we should reduce the number of papers actually consumed for printing, by fitting as many receipts in single paper (We had cheap manpower to cut the pages manually.) Ordering of receipts was immaterial.
So given a simple list of (receipt no, #lines), how do you re-order them and create groupings so that each of that group size is less than 66 (in this case), and yet, the wasted size from all groups is minimized?
When I was still a graduate student (1980's), I was helping out some local businesses. There was a need to print a lot of receipts, and these receipts would be of some size, measured in number of lines. Say 10, 35, 20, 5, 12 etc. The paper size would be about 60 lines.
And then, we thought we should reduce the number of papers actually consumed for printing, by fitting as many receipts in single paper (We had cheap manpower to cut the pages manually.) Ordering of receipts was immaterial.
So given a simple list of (receipt no, #lines), how do you re-order them and create groupings so that each of that group size is less than 66 (in this case), and yet, the wasted size from all groups is minimized?
It is famous Knapsack problem.