程序员竞赛：在页面上拟合图片 [英] Programmers Contest: Fit pictures on a page
问题描述
GLOSSY：本月夏季程序员正在进行中！
截止日期是2005年9月30日
http://dinsights.com/POTM
-------------------- -------------------------------------------------- ----------
我喜欢拍摄数码照片，但那张漂亮的光面相纸
很贵！因此，当我可爱的妻子要求打印一堆
的照片时，我总是试着把它们放在一张纸上。
夏天的POTM挑战你写一个程序，在一张纸上放置最少剩余的b / 26美元b / b
空间。
-------------------------------------------------- ------------------------------
本月程序员（POTM）是一个公正的 - 有趣的节目
与活跃的论坛和超过1100名成员的比赛（我们通常
为每个POTM挑战获得40-50个参赛作品）。支持的语言
包括C / C ++ / Perl / Ruby / PHP / Python / awk / shell。
重点是算法和编程的乐趣。
如果听起来很有趣，请访问 http://dinsights.com / POTM ......
= Fred（又名POTM-MASTER）
GLOSSY: The Summer Programmer Of The Month Contest is underway!
Deadline is September 30, 2005
http://dinsights.com/POTM
--------------------------------------------------------------------------------
I love taking digital pictures, but that nice glossy photo paper
is expensive! So when my lovely wife asks for prints of a bunch
of pictures, I always try and fit them onto a single piece of paper.
The summer POTM challenges you to write a program that will place up to
26 pictures on a sheet of paper with the least amount of leftover
space.
--------------------------------------------------------------------------------
The Programmer Of The Month (POTM) is a just-for-fun programming
contest with an active forum and over 1100 members (we usually
get 40-50 entries for each POTM challenge). Supported languages
include C/C++/Perl/Ruby/PHP/Python/awk/shell.
Emphasis is on the algorithms and the joy of programming.
If it sounds like fun, please visit at http://dinsights.com/POTM ...
=Fred (a.k.a. The POTM-MASTER)
推荐答案
这不是NP完全问题还是我疯了？
Isn''t that an NP-complete problem or am I crazy?
Chung Leong写道：
Chung Leong wrote:
这不是NP完全问题还是我疯了？
Isn''t that an NP-complete problem or am I crazy?
这使得它成为一个更现实的挑战，没有是吗？
假设它很简单，就像计算一个
最小生成树一样。每个程序都会生成
相同的输出。会是什么样的比赛？
That makes it a more realistic challange, doesn''t it?
Suppose it was something simple, like calculating a
minimal spanning tree. Every program would produce the
same output. What kind of contest would that be?
Chung Leong写道：
Chung Leong wrote:
这不是NP - 完全问题还是我疯了？
Isn''t that an NP-complete problem or am I crazy?
这是完整的NP。它被称为切割原料问题。 （又名Knapsack
问题）。这是描述它的维基百科页面：
http： //en.wikipedia.org/wiki/Cutting_stock_problem
有一些商业应用可以解决用于木工行业的2D
的问题（以及其他）。通常这样做是为了最大限度地减少将面板（胶合板等）切割成较小的橱柜等b
件时的浪费。
-Don
It is NP complete. Its known as the "cutting stock problem" (aka "Knapsack
problem"). Here''s a Wikipedia page that describes it:
http://en.wikipedia.org/wiki/Cutting_stock_problem
There are commerical applications available that "solve" the problem in 2D
for use in the woodworking industry (among others). This is generally done
to minimize waste when cutting down panels (plywood, etc) into smaller
pieces for cabinets, etc.
-Don
这篇关于程序员竞赛：在页面上拟合图片的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
