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.

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.

# 承

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)

# 转

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