Question

Помогите пожалуйста решить задачу. Желательно C++ питон, но можно и паскаль. ПутешествиеОдин торговец собрался в дорогу. У него имеется N предметов (N≤20). Известны вес и стоимость каждого предмета. Помогите ему заполнить рюкзак предметами так, чтобы суммарная стоимость предметов в рюкзаке была максимальна. Рюкзак может выдержать не более 40 кг веса. Величины веса и стоимости – натуральные числа ≤100.Формат вводаВ первой строке вводится количество предметов N. Со второй строки через пробел вводится вес и стоимость предмета соответственно.Формат выводаВыводятся номера предметов, которые взяли в рюкзак в любом порядке. Выводится вес и стоимость всех предметов в рюкзаке.Ввод 310 1419 1212 15Вывод3122 29

Answer 1

Ответ:

Вот код на питоне:

N = int(input())

objects = []

for i in range(N):

   objects.append(list(map(int, input().split())))

rezult = []

summ = 0

price = 0

while summ <= 40:

   Max = 0

   index = -1

   for i in objects:

       if i[1] > Max and i[0] + summ <= 40 and not objects.index(i) in rezult:

           Max = i[1]

           index = objects.index(i)

   if index == -1:

       break

   rezult.append(index)

   summ += objects[index][0]

   price += objects[index][1]

for i in rezult:

   print(i + 1)

print(summ, price)

Объяснение:

При необходимости могу пояснить построчно.

Answer 2

To solve this problem, we can use a dynamic programming approach known as the 0/1 Knapsack problem. The goal is to maximize the total value of the items in the backpack without exceeding its weight capacity.

Here's an example solution in Python:

def knapsack(N, weights, values):
    # Create a table to store the maximum values for different weights and items
    dp = [[0] * (41) for _ in range(N + 1)]

# Iterate through each item
    for i in range(1, N + 1):
        # Iterate through each possible weight
        for w in range(1, 41):
            # If the current item's weight is less than or equal to the current weight limit
            if weights[i - 1] <= w:
                # Calculate the maximum value by either including or excluding the current item
                dp[i][w] = max(dp[i - 1][w], values[i - 1] + dp[i - 1][w - weights[i - 1]])
            else:
                # If the current item's weight exceeds the current weight limit, exclude it
                dp[i][w] = dp[i - 1][w]

# Find the items included in the knapsack
    included_items = []
    w = 40
    for i in range(N, 0, -1):
        if dp[i][w] != dp[i - 1][w]:
            included_items.append(i)
            w -= weights[i - 1]

# Reverse the order of included items for correct output
    included_items.reverse()

# Calculate the total weight and value of the included items
    total_weight = sum(weights[i - 1] for i in included_items)
    total_value = sum(values[i - 1] for i in included_items)

return included_items, total_weight, total_value

# Read input
N = int(input())
weights = []
values = []
for _ in range(N):
    w, v = map(int, input().split())
    weights.append(w)
    values.append(v)

# Solve the problem
included_items, total_weight, total_value = knapsack(N, weights, values)

# Print the output
print(' '.join(str(i) for i in included_items))
print(total_weight, total_value)

This code takes the number of items `N` as input, followed by the weight and value of each item. It then uses the `knapsack` function to find the items to include in the backpack and calculates the total weight and value of the included items. Finally, it prints the included item numbers and the total weight and value.

Please note that the code assumes the input is correctly formatted and within the given constraints.