如何修复Box Stacking Algorithm中重复使用同一盒子的问题？

Ah, I see the root issue here! Your current check only ensures that the current rotation rot[i] isn't the same physical box as rot[j], but it doesn't account for cases where the stack leading to msh[j] already includes the same physical box as rot[i]. That's why you're getting duplicate box uses—your DP state doesn't track which boxes have already been included in the stack.

Let's fix this by modifying the dynamic programming state to track both the maximum height and the set of boxes used to reach that height. Since we're dealing with a small number of boxes, we can use a bitmask to efficiently represent used boxes (each bit in an integer corresponds to whether a box is used).

Fixed Code #

class Box:
    def __init__(self,l, w, h):
        self.h = h
        self.w = w
        self.l = l
        self.boxNo = 0
    def __lt__(self,other):
        return self.l * self.w < other.l * other.w

def maxStackHeight(arr, n):
    # Create an array of all rotations of given boxes.
    rot = [Box(0, 0, 0) for _ in range(3 * n)]
    index = 0
    no=1
    for i in range(n):
        # Original box (height as given, sorted base sides)
        rot[index].h = arr[i].h
        rot[index].l = max(arr[i].l, arr[i].w)
        rot[index].w = min(arr[i].l, arr[i].w)
        rot[index].boxNo = no
        index += 1
        # First rotation (width becomes height)
        rot[index].h = arr[i].w
        rot[index].l = max(arr[i].h, arr[i].l)
        rot[index].w = min(arr[i].h, arr[i].l)
        rot[index].boxNo = no
        index += 1
        # Second rotation (length becomes height)
        rot[index].h = arr[i].l
        rot[index].l = max(arr[i].h, arr[i].w)
        rot[index].w = min(arr[i].h, arr[i].w)
        rot[index].boxNo = no
        index += 1
        no += 1
    
    # Sort rotations in descending order of base area (l*w)
    rot.sort(reverse=True)
    total_rotations = 3 * n
    
    # DP state: each element is a tuple (max_height, used_boxes_bitmask)
    # Bitmask: each bit represents if a 1-based box number is used
    msh = [ (rot[i].h, 1 << (rot[i].boxNo - 1)) for i in range(total_rotations) ]
    
    # Compute optimized stack heights in bottom-up manner
    for i in range(total_rotations):
        for j in range(i):
            # Get bitmask for the current rotation's physical box
            current_box_mask = 1 << (rot[i].boxNo - 1)
            # Check two critical conditions:
            # 1. Current rotation's base fits under the j-th rotation's base
            # 2. The current physical box hasn't been used in j's stack
            if (rot[i].w <= rot[j].w and rot[i].l <= rot[j].l) and (msh[j][1] & current_box_mask) == 0:
                if msh[i][0] < msh[j][0] + rot[i].h:
                    # Update height and add current box to the used mask
                    msh[i] = (msh[j][0] + rot[i].h, msh[j][1] | current_box_mask)
    
    # Find the maximum possible stack height
    max_height = -1
    # Optional: Uncomment below to only consider stacks that use ALL boxes (like your example)
    # full_box_mask = (1 << n) - 1
    # for height, mask in msh:
    #     if mask == full_box_mask and height > max_height:
    #         max_height = height
    # Default: Get maximum height regardless of how many boxes are used
    for height, mask in msh:
        if height > max_height:
            max_height = height
    return max_height

arr = [Box(4,5,2),Box(3,1,6),Box(3,2,1),Box(6,8,3)]
n = len(arr)
print("The maximum possible height of stack is",maxStackHeight(arr, n))

Key Changes Explained #

1. DP State Enhancement: Instead of storing just the height in msh, we now store a tuple (max_height, used_boxes_bitmask). The bitmask uses one bit per original box (all rotations of the same box share the same boxNo).
2. Initialization: Each rotation starts with its own height and a bitmask where only its box's bit is set—representing a stack with just that single rotation.
3. Strict Usage Check: When stacking rot[i] on top of rot[j]'s stack, we now verify that rot[i]'s physical box hasn't been used in rot[j]'s stack (via bitmask comparison).
4. State Update: If valid, we update the height and combine the bitmasks to mark the current box as used.

This fix ensures no physical box is used more than once, while still allowing us to explore all valid rotations and stack combinations. For your example input, it will correctly return the expected height of 22 using all four boxes exactly once.

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