Cleen Team Algorithm Test
in python with 0 comment

Cleen Team Algorithm Test

in python with 0 comment

A company has an machine for cutting sheet metal. Given a rectangular sheet of metal that is H feet high and W feet wide, this machine can cut through the entire sheet either horizontally or vertically. Each day, the company downloads() a list of orders for rectangular pieces of sheet metal. This list consists of n entries, where for 1 <= i <= n, hi x wi denotes the height and width of the piece, and pi denotes the profit for selling a piece of this size.(The metal has a directional surface finish, so you cannot use a 5 x 3 piece to fill an order for a 3 x 5 piece.) Orders may be filled multiple times, so if a piece of a certain size is worth 5USD, the company would receive 15USD for generating three copies of this piece. Any leftover pieces that are not on the order list are wasted and cost 1USD each, irrespective of their size. The company wants you to write a problem that determines the sequence of cuts to produce the maximum total profit.

PkMClD.png

For example, part a show an input consisting of a sheet of size 12x20. There are n = 3 orders as shown in the figure (the blue, green, and red rectangles). Part b we show a possible solution, of total profit (2 * 15USD + 2 * 8USD + 2 * 3USD) — 3 * 1USD = 49USD.

In this problem you will develop a python program that takes as input H, W, and the arrays h[1..n], w[1..n], and p[1..n] and determines the sequence of cuts to maximize profit. You may assume that all the input quantities are positive integers.

Finish your program with a python program, in your program, it should include test data as shown above and by running your program should produce the right output max profit=49.

Push your program to you GitHub account and send me the link.


一家公司有一个用来切割金属板的机器。给定一个高度为H英尺和W英尺宽的矩形金属片,该机器可以水平或垂直切割整个片材。公司每天下载()一张矩形金属片订单清单。该订单由n项组成,其中 1 <= i <= n,hi x wi表示该件的高度和宽度,而pi表示销售该尺寸的一块的利润。(金属具有定向的表面光洁度,所以你不能使用5 x 3大小的金属片来替代3 x 5大小的金属片。)订单中的某一项可能会有多次,如果某件尺寸的某件产品价值5美元,生产3张这样的产品,公司将会收到15美元。任何不在订单上的剩余物品都会被浪费,这种物品每个价值1美元,无论尺寸大小。该公司希望你写出一个程序,确定裁剪的顺序,以产生最大的总利润。

PkMClD.png

例如,a部分显示一个由12x20大小的金属板。如图所示,有n = 3个订单(蓝色,绿色和红色矩形)。b部分我们展示了一个可能的解决方案,即总利润(2 x 15USD + 2 x 8USD + 2 x 3USD) - 3 x 1USD = 49USD

在这个问题中,你将开发一个 Python 程序,它接受输入H,W和数组h [1..n],w [1..n]和p [1..n]并确定切割顺序实现利润最大化。假设所有输入量都是正整数。

用Python来完成你的程序,在你的程序中,它应该包含如上所示的测试数据,并且通过运行你的程序应该产生正确的输出最大利润=49。

把你的程序放在GitHub上,发给我链接。

这道题是一个典型的 DP 的题目,除了最原始的背包问题之外我对于 DP 的了解十分有限。硬着头皮分析了一波:

对于1 ≤ a ≤ H, 1 ≤ b ≤ W,通过切割金属片高度 a 和宽度 b 使利润profit(a, b)获得最大值。

假设函数p(a, b),如果存在 i 满足hi=a,wi=b,该函数返回利润 pi;否则返回-1。所以有以下三种情况:

A:不需要任何切割,利润为p(a, b)

B:在某处水平切割,将钢板切割成两部分,满足1 ≤ y ≤ a-1。这样产生了两块钢板(a-y)×b 和 y×b,此时利润为 profit(y, b) + profit(a-y, b)

C:在某处垂直切割,将钢板切割成两部分,满足1 ≤ x ≤ b-1。这样产生了两块钢板a×(b-x)和 a×x,此时利润为 profit(a, x) + profit(a, b−x)

PeI2Pf.png

即使有了思路但是代码实现起来也十分困难:

class Solution():
    def __init__(self, w, h, sub_w, sub_h, p):
        self.w = w
        self.h = h
        self.value_dict = dict()
        for x, y, z in zip(sub_w, sub_h, p):
            self.value_dict.setdefault('{x}x{y}'.format(x=x, y=y), z)

    def value(self, x, y):
        return self.value_dict.get('{x}x{y}'.format(x=x, y=y), None)

    def profit(self, x, y):
        pass

    def p(self, x, y):
        return self.value(x=x, y=y) or -1

    def run(self):
        pass


def test():
    solution = Solution(
        w=20, h=12, sub_w=[4, 5, 8], sub_h=[5, 5, 7], p=[3, 8, 15])
    solution.run()


if __name__ == '__main__':
    test()
Responses