找到具有 2 个值的项目的最佳组合

Question

我有一个包含 500 个元素的列表，每个元素都有 2 个值 x（0-无穷大的浮点值）和 y（0-1 的浮点值）。我需要找到这些元素中 10 个的最便宜（最低 sum(x)）组合，以实现小于给定 n 的平均 y 值。我环顾四周，认为这是某种背包问题，但我不确定如何在线解决我的具体问题，并担心它可能太复杂。任何帮助将不胜感激。

到目前为止我所尝试的只是尝试 ChatGPT 的解决方案，但我认为它的复杂性太高了。我正在寻找一种希望可以用大量元素完成的解决方案 <1000.

def find_cheapest_combination(elements, k, target_avg):
    def backtrack(start, combo):
        if len(combo) == k:
            # Calculate the average float value for the current combination
            avg_float = sum(element[1] for element in combo) / k
            if avg_float <= target_avg:
                nonlocal best_combo, lowest_avg
                best_combo = combo[:]
                lowest_avg = avg_float
            return

        for i in range(start, len(elements)):
            if len(elements) - i < k - len(combo):
                # Not enough elements remaining to form a valid combination
                break
            combo.append(elements[i])
            backtrack(i + 1, combo)
            combo.pop()

    elements.sort(key=lambda x: x[0])  # Sort by price in ascending order
    best_combo = []
    lowest_avg = float('inf')
    backtrack(0, [])

    return best_combo


elements = [(x, y) for x, y in items]
k = 10
target_avg = 0.07
cheapest_combination = find_cheapest_combination(elements, k, target_avg)
print(cheapest_combination)

Answer 1

我真的不认为需要动态规划方法来解决这个问题。

您可以使用滑动窗口技术来解决这个问题。解决方案如下。

第 1 步：按第一个元素 (x) 对给定数组进行排序

第2步：分别获取前10个x值和y值的总和。

第3步：检查y值之和的平均值是否小于目标值。如果是这样，您已经找到解决方案了。

第 4 步：否则，您已将窗口滑动一个元素并再次执行相同的操作。

排序在这种方法中起作用的原因是因为您需要找到 10 个 x 值的总和并最小化总和。将其视为选择最小元素来创建总和。例如，如果您有一个数组 [10, 2, 4, 17]，并且您想要找到 2 个元素的最小总和，则必须选择 2 和 4，它们是最小元素。

这里是使用滑动窗口技术解决您的问题的示例代码：

import random

# 500 elements in the list
input_list = [[random.randint(1, 100), random.randint(1, 100)] for _ in range(500)]

target_val = 50

# Task: Minimize the sum of 10 elements(x) while keeping sum of corresponding y values less
# less than target_val

# Step 1: Sort the list based on x values
input_list.sort(key=lambda x: x[0])

# Step 2: Take a window of size 10 and find the sum of x values and corresponding y values
window_x_sum = 0
window_y_sum = 0

for i in range(10):
    window_x_sum += input_list[i][0]
    window_y_sum += input_list[i][1]

left_pointer = 0
right_pointer = 10

# Before we start moving the window, we need to check whether the window_y satisfies the condition
# If it does, we have already found the solution
if (window_y_sum / 10) < target_val:
    print("Solution found")
    print("Window: ", input_list[left_pointer:right_pointer])
    print("Window x sum: ", window_x_sum)
    print("Window y sum: ", window_y_sum)
else:
    while right_pointer < 500:
        window_x_sum -= input_list[left_pointer][0]
        window_y_sum -= input_list[left_pointer][1]
        left_pointer += 1
        window_x_sum += input_list[right_pointer][0]
        window_y_sum += input_list[right_pointer][1]
        right_pointer += 1
        if (window_y_sum / 10) < target_val:
            print("Solution found")
            print("Window: ", input_list[left_pointer:right_pointer])
            print("Window x sum: ", window_x_sum)
            print("Window y sum: ", window_y_sum)
            break