如何在First-fit装箱算法中获取各箱子的物品内容而非仅数量？

Got it, let's fix this up. The First-Fit algorithm works by shoving each item into the first bin that has enough leftover space—right now you're probably just counting bins, but to track what's inside each one, you just need to adjust how you store your bins. Instead of only tracking remaining capacity or bin count, you'll want to keep a record of the actual items in each bin as you go.

Here's the step-by-step approach: #

• Use a nested data structure: Instead of a list of numbers (for remaining capacity), use a list where each element is either a sublist (holding items in the bin) or a dictionary (tracking both items and remaining space for efficiency).
• Iterate through each item: For every item, check existing bins one by one. If the item fits in a bin, add it to that bin. If none fit, create a new bin and add the item to it.
• Output the results: Once all items are placed, loop through your bin structure to print each bin's contents.

Example Code (Python) #

First, a simple version that uses sublists (easy to read, great for small datasets):

def first_fit_track_contents(items, bin_capacity):
    bins = []  # Each element is a list representing items in a bin

    for item in items:
        placed = False
        # Check each existing bin for space
        for bin in bins:
            if sum(bin) + item <= bin_capacity:
                bin.append(item)
                placed = True
                break
        # If no bin had space, create a new one
        if not placed:
            bins.append([item])

    # Print the final bin contents
    for idx, bin in enumerate(bins, start=1):
        print(f"bin{idx}={bin}")
    return bins

# Test with your sample input
items = [8, 1, 4, 2, 1, 4]
bin_capacity = 10
first_fit_track_contents(items, bin_capacity)

Output for your input:

bin1=[8, 1, 1]
bin2=[4, 2, 4]

Note: This matches standard First-Fit behavior (processing items in input order). Your sample output looks like it might be using First-Fit Decreasing (sorting items largest to smallest first), but if you strictly need First-Fit, this is the correct result.

Optimized Version (For Larger Datasets) #

Calculating sum(bin) every time can get slow with lots of items. Instead, track remaining space explicitly with a dictionary:

def first_fit_optimized(items, bin_capacity):
    bins = []  # Each element is {'contents': [], 'remaining': int}

    for item in items:
        placed = False
        for bin in bins:
            if bin['remaining'] >= item:
                bin['contents'].append(item)
                bin['remaining'] -= item
                placed = True
                break
        if not placed:
            bins.append({
                'contents': [item],
                'remaining': bin_capacity - item
            })

    # Print results
    for idx, bin in enumerate(bins, start=1):
        print(f"bin{idx}={bin['contents']}")
    return bins

Key Takeaway #

The main change is shifting from tracking just bin count/capacity to tracking the actual items in each bin. This way, once the algorithm finishes placing all items, you have a direct record of what's in every bin—no extra work needed to reconstruct it later.

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