编辑代码

# coding:utf-8
#JSRUN引擎2.0,支持多达30种语言在线运行,全仿真在线交互输入输出。 
import numpy as np
import random
import math

# Data for the problem
weights = df['重量(g)'].values
values = df['价值(元)'].values
n = len(weights)
max_weight = 500  # Maximum weight for the backpack

# Simulated Annealing Algorithm
def simulated_annealing(weights, values, max_weight, T_init=1000, T_min=1, alpha=0.95, max_iterations=1000):
    # Initial solution: Randomly select items (0 or 1) for the knapsack
    current_solution = np.random.randint(2, size=n)
    current_weight = np.sum(weights * current_solution)
    current_value = np.sum(values * current_solution)

    # Initialize best solution
    best_solution = current_solution.copy()
    best_weight = current_weight
    best_value = current_value

    T = T_init  # Starting temperature

    for iteration in range(max_iterations):
        # Generate a neighbor by flipping one random bit (item included or excluded)
        neighbor_solution = current_solution.copy()
        flip_index = random.randint(0, n - 1)
        neighbor_solution[flip_index] = 1 - neighbor_solution[flip_index]

        # Calculate the weight and value of the neighbor solution
        neighbor_weight = np.sum(weights * neighbor_solution)
        neighbor_value = np.sum(values * neighbor_solution)

        # Check if the neighbor is feasible (does not exceed the weight limit)
        if neighbor_weight <= max_weight:
            # Accept the neighbor with a certain probability
            delta_value = neighbor_value - current_value
            if delta_value > 0 or random.random() < math.exp(delta_value / T):
                current_solution = neighbor_solution
                current_weight = neighbor_weight
                current_value = neighbor_value

                # Update the best solution found
                if current_value > best_value:
                    best_solution = current_solution.copy()
                    best_weight = current_weight
                    best_value = current_value

        # Decrease the temperature
        T *= alpha

        # Stop if the temperature is below the minimum threshold
        if T < T_min:
            break

    return best_solution, best_weight, best_value

# Run the simulated annealing algorithm
best_solution, best_weight, best_value = simulated_annealing(weights, values, max_weight)

# Get the selected items based on the solution
selected_items = np.where(best_solution == 1)[0] + 1  # +1 to match the 物品编号

# Return the result
selected_items, best_weight, best_value