Constructive Heuristics for Knapsack Problem

Problem

The Knapsack Problem is a classic combinatorial optimization problem where items with weights and values must be selected to maximize total value without exceeding capacity.

• Given: A set of items, each with a weight and value, and a knapsack with limited capacity

• Objective: Maximize the total value of selected items

• Constraints: Total weight cannot exceed knapsack capacity

Algorithm Design Task

Constructive heuristics iteratively select items to add to the knapsack. The task is to design the heuristic for selecting the next item in each iteration.

• Inputs: Remaining capacity, remaining items (weight, value, index)

• Outputs: Selected item (weight, value, index) or None

Evaluation

• Dataset: 32 instances, 50 items, capacity = 100

• Fitness: Average total value (maximized)

Template

template_program = '''
import numpy as np

def select_next_item(remaining_capacity: int, remaining_items: List[Tuple[int, int, int]]) -> Tuple[int, int, int] | None:
    """
    Select the item with the highest value-to-weight ratio that fits in the remaining capacity.

    Args:
        remaining_capacity: The remaining capacity of the knapsack.
        remaining_items: List of tuples containing (weight, value, index) of remaining items.

    Returns:
        The selected item as a tuple (weight, value, index), or None if no item fits.
    """
    best_item = None
    best_ratio = -1

    for item in remaining_items:
        weight, value, index = item
        if weight <= remaining_capacity:
            ratio = value / weight
            if ratio > best_ratio:
                best_ratio = ratio
                best_item = item

    return best_item
'''

task_description = '''
Given a set of items with weights and values, the goal is to select a subset of items
that maximizes the total value while not exceeding the knapsack's capacity.
Help me design a novel algorithm to select the next item in each step.
'''

Configuration Parameters

Parameter	Description	Default
timeout_seconds	Maximum evaluation time	20
n_instance	Number of problem instances	32
n_items	Number of items	50
knapsack_capacity	Knapsack capacity	100

Example Usage

from llm4ad.task.optimization.knapsack_construct import KnapsackEvaluation

evaluator = KnapsackEvaluation()

def select_next_item(remaining_capacity, remaining_items):
    # Greedy by value-to-weight ratio
    best_item = None
    best_ratio = -1
    for item in remaining_items:
        weight, value, index = item
        if weight <= remaining_capacity:
            ratio = value / weight
            if ratio > best_ratio:
                best_ratio = ratio
                best_item = item
    return best_item

result = evaluator.evaluate_program('', select_next_item)