from typing import List, Dict, Any, Tuple

def solve_dp(items: List[Dict[str, int]], capacity: int) -> Dict[str, Any]:
    """
    Dynamic Programming solution for 0/1 Knapsack.
    O(N * W)
    """
    n = len(items)
    # dp[i][w] = max value using first i items with capacity w
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]
    
    for i in range(1, n + 1):
        item = items[i-1]
        w, v = item["weight"], item["value"]
        for j in range(capacity + 1):
            if w <= j:
                dp[i][j] = max(dp[i-1][j], dp[i-1][j-w] + v)
            else:
                dp[i][j] = dp[i-1][j]
    
    max_value = dp[n][capacity]
    
    # Backtrack to find selected items
    selected_indices = []
    w = capacity
    for i in range(n, 0, -1):
        if dp[i][w] != dp[i-1][w]:
            item = items[i-1]
            selected_indices.append(item["id"])
            w -= item["weight"]
            
    return {
        "max_value": max_value,
        "selected_items": selected_indices
    }

def solve_backtracking(items: List[Dict[str, int]], capacity: int) -> Dict[str, Any]:
    """
    Backtracking solution for 0/1 Knapsack.
    O(2^N)
    """
    n = len(items)
    max_val = 0
    best_selection = []
    
    def backtrack(index, current_weight, current_value, selection):
        nonlocal max_val, best_selection
        
        if current_weight > capacity:
            return

        if current_value > max_val:
            max_val = current_value
            best_selection = selection[:]
            
        if index == n:
            return

        # Include current item
        item = items[index]
        if current_weight + item["weight"] <= capacity:
            selection.append(item["id"])
            backtrack(index + 1, current_weight + item["weight"], current_value + item["value"], selection)
            selection.pop()
            
        # Exclude current item
        backtrack(index + 1, current_weight, current_value, selection)

    backtrack(0, 0, 0, [])
    return {
        "max_value": max_val,
        "selected_items": best_selection
    }