# coding:utf-8#JSRUN引擎2.0,支持多达30种语言在线运行,全仿真在线交互输入输出。 importnumpy as npimportrandomimportmath
# Data for the problemweights = df['重量(g)'].valuesvalues = df['价值(元)'].valuesn = len(weights)max_weight = 500 # Maximum weight for the backpack
# Simulated Annealing Algorithmdefsimulated_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 knapsackcurrent_solution = np.random.randint(2, size=n)current_weight = np.sum(weights * current_solution)current_value = np.sum(values * current_solution)
# Initialize best solutionbest_solution = current_solution.copy()best_weight = current_weightbest_value = current_valueT = T_init # Starting temperatureforiteration 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 solutionneighbor_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)ifneighbor_weight <= max_weight: # Accept the neighbor with a certain probabilitydelta_value = neighbor_value - current_valueifdelta_value > 0 or random.random() < math.exp(delta_value / T):current_solution = neighbor_solutioncurrent_weight = neighbor_weightcurrent_value = neighbor_value
# Update the best solution foundifcurrent_value > best_value:best_solution = current_solution.copy()best_weight = current_weightbest_value = current_value
# Decrease the temperatureT*= alpha
# Stop if the temperature is below the minimum thresholdifT < T_min:breakreturnbest_solution, best_weight, best_value
# Run the simulated annealing algorithmbest_solution,best_weight, best_value = simulated_annealing(weights, values, max_weight)
# Get the selected items based on the solutionselected_items = np.where(best_solution == 1)[0] + 1 # +1 to match the 物品编号
# Return the resultselected_items,best_weight, best_value