基于动态规划的二维矩形板材切割优化问题求解咨询

Got it, let's tackle this dynamic programming problem head-on. You need to maximize the total value of cutting a rectangular plate into specified elements (no rotation allowed, some can be used infinitely) AND track the tree structure of cuts—we'll cover both parts clearly.

First, let's clarify the core of this problem: it's a 2D extension of the classic cutting stock problem, mixed with elements of the unbounded and 0-1 knapsack problems. The twist is we need to not only compute the maximum value but also map out exactly how the cuts/placements are made (the tree structure).

We'll use a memoized recursive approach (top-down DP) since it's easier to track the cut structure alongside value. Here's how we define our state:

• dp[w][h][remaining_counts]: The maximum value we can get from a plate of width w and height h, with remaining_counts being a tuple tracking how many of each finite-use element we have left (infinite elements get a stand-in like inf since we never run out).
• We'll also maintain a cut_tracker dictionary that stores the optimal action (place an element, split horizontally, split vertically) for each state—this is how we'll build our cut tree later.

For each state (w, h, remaining_counts), we consider three possible actions and pick the one that gives the highest value:

1. Place an Element #

For every element type:

• Skip if the element's width/height is larger than the current plate.
• For finite elements, skip if we have none left.
• Calculate the value of placing this element (add its value) plus the maximum value from the two remaining non-overlapping regions: the strip to the right of the element (w - elem.width, h) and the strip below it (elem.width, h - elem.height).
• Update the remaining_counts if it's a finite element (decrement its count by 1).

2. Split the Plate Horizontally #

Iterate over all possible split heights h1 (from 1 to h-1). The total value is the sum of the maximum values from the top plate (w, h1) and the bottom plate (w, h - h1).

3. Split the Plate Vertically #

Similar to horizontal splitting: iterate over all possible split widths w1 (from 1 to w-1), sum the values of the left plate (w1, h) and right plate (w - w1, h).

We take the maximum value from all these options and store the corresponding action in cut_tracker.

Once we've filled our dp and cut_tracker tables, we can recursively build the tree from the original plate size:

• If the state is an empty plate (w or h ≤ 0), return a null/empty node.
• If the optimal action was placing an element, create a node for that element, then recursively add nodes for the two remaining regions.
• If the action was a split, create a split node, then add nodes for the two resulting sub-plates.

Here's a Python implementation that ties this all together:

from typing import List, Tuple, Dict, Optional

class Element:
    def __init__(self, elem_id: int, width: int, height: int, value: int, is_unbounded: bool):
        self.id = elem_id
        self.width = width
        self.height = height
        self.value = value
        self.is_unbounded = is_unbounded

def solve_plate_cutting(plate_width: int, plate_height: int, elements: List[Element]) -> Tuple[int, Optional[Dict]]:
    # Memoization tables: use tuples as keys for immutability
    dp: Dict[Tuple[int, int, Tuple[int]], int] = {}
    cut_tracker: Dict[Tuple[int, int, Tuple[int]], Tuple] = {}

    def helper(w: int, h: int, remaining: Tuple[int]) -> int:
        # Base case: empty plate has no value
        if w <= 0 or h <= 0:
            return 0
        
        key = (w, h, remaining)
        if key in dp:
            return dp[key]
        
        max_value = 0
        best_action = None

        # Try placing each element
        for idx, elem in enumerate(elements):
            if elem.width > w or elem.height > h:
                continue
            # Skip if finite element is exhausted
            if not elem.is_unbounded and remaining[idx] <= 0:
                continue
            
            # Update remaining counts for finite elements
            new_remaining = list(remaining)
            if not elem.is_unbounded:
                new_remaining[idx] -= 1
            new_remaining_tuple = tuple(new_remaining)

            # Calculate value: element value + remaining regions
            current_value = elem.value + helper(w - elem.width, h, new_remaining_tuple) + helper(elem.width, h - elem.height, new_remaining_tuple)
            if current_value > max_value:
                max_value = current_value
                best_action = ("place", idx, new_remaining_tuple)
        
        # Try horizontal splits
        for split_h in range(1, h):
            split_value = helper(w, split_h, remaining) + helper(w, h - split_h, remaining)
            if split_value > max_value:
                max_value = split_value
                best_action = ("split_horizontal", split_h)
        
        # Try vertical splits
        for split_w in range(1, w):
            split_value = helper(split_w, h, remaining) + helper(w - split_w, h, remaining)
            if split_value > max_value:
                max_value = split_value
                best_action = ("split_vertical", split_w)
        
        dp[key] = max_value
        cut_tracker[key] = best_action
        return max_value

    # Initialize remaining counts: inf for unbounded, initial count (here 1) for finite
    initial_remaining = []
    for elem in elements:
        if elem.is_unbounded:
            initial_remaining.append(float('inf'))
        else:
            initial_remaining.append(1)  # Adjust this to your actual initial counts
    initial_remaining_tuple = tuple(initial_remaining)

    total_max_value = helper(plate_width, plate_height, initial_remaining_tuple)

    # Build the cut tree
    def build_tree(w: int, h: int, remaining: Tuple[int]) -> Optional[Dict]:
        if w <= 0 or h <= 0:
            return None
        
        key = (w, h, remaining)
        action = cut_tracker.get(key)
        if not action:
            return {"type": "empty", "width": w, "height": h}
        
        action_type = action[0]
        if action_type == "place":
            elem_idx, new_remaining = action[1], action[2]
            elem = elements[elem_idx]
            return {
                "type": "place_element",
                "element_id": elem.id,
                "element_width": elem.width,
                "element_height": elem.height,
                "element_value": elem.value,
                "plate_width": w,
                "plate_height": h,
                "children": [
                    build_tree(w - elem.width, h, new_remaining),
                    build_tree(elem.width, h - elem.height, new_remaining)
                ]
            }
        elif action_type == "split_horizontal":
            split_h = action[1]
            return {
                "type": "split_horizontal",
                "plate_width": w,
                "plate_height": h,
                "split_height": split_h,
                "children": [
                    build_tree(w, split_h, remaining),
                    build_tree(w, h - split_h, remaining)
                ]
            }
        elif action_type == "split_vertical":
            split_w = action[1]
            return {
                "type": "split_vertical",
                "plate_width": w,
                "plate_height": h,
                "split_width": split_w,
                "children": [
                    build_tree(split_w, h, remaining),
                    build_tree(w - split_w, h, remaining)
                ]
            }
        return None

    cut_tree = build_tree(plate_width, plate_height, initial_remaining_tuple)
    return total_max_value, cut_tree

• State Space: If your plate dimensions are large, using a dictionary (instead of a 3D array) for memoization saves space since we only compute states we actually need.
• Finite Elements: If you have many finite element types, the remaining_counts tuple can get large. You can optimize by only tracking counts for finite elements (ignore unbounded ones in the tuple) to reduce state complexity.
• No Rotation: We strictly respect element dimensions—no swapping width/height, which aligns with your constraint.
• Tree Structure: The resulting tree is a nested dictionary where each node represents either a split or an element placement, with children nodes representing subsequent operations on sub-plates.

内容的提问来源于stack exchange，提问作者Mateusz Sadowski