写一段动态规划求解01背包问题的算法代码

// 动态规划求解01背包问题的算法代码：

int knapsack(int W, int wt[], int val[], int n)
{
int i, w;
int K[n+1][W+1];

// Build table K[][] in bottom up manner
for (i = 0; i <= n; i++)
{
for (w = 0; w <= W; w++)
{
if (i==0 || w==0)
K[i][w] = 0;
else if (wt[i-1] <= w)
K[i][w] = max(val[i-1] + K[i-1][w-wt[i-1]], K[i-1][w]);
else
K[i][w] = K[i-1][w];
}
}

return K[n][W];
}

相关问题

写一段python代码用贪心算法求解背包问题

下面是一个基于贪心算法的背包问题的 Python 代码示例：

def knapsack(max_weight, items):
    """
    :param max_weight: 背包最大容量
    :param items: 物品列表，每个物品是一个元组 (weight, value)
    :return: 最大总价值，选择的物品列表
    """
    # 按照单位重量价值排序
    items = sorted(items, key=lambda x: x[1] / x[0], reverse=True)
    total_value = 0
    selected_items = []
    for weight, value in items:
        if max_weight >= weight:
            max_weight -= weight
            total_value += value
            selected_items.append((weight, value))
        else:
            # 当前物品不能全部放入背包，只能选取一部分
            fraction = max_weight / weight
            total_value += fraction * value
            selected_items.append((fraction * weight, fraction * value))
            break
    return total_value, selected_items

该函数接受两个参数，分别是背包最大容量 `max_weight` 和物品列表 `items`。每个物品是一个元组，包含两个值，分别表示物品的重量和价值。函数返回两个值，分别是最大总价值和选择的物品列表。

该函数的实现基于一个贪心思想：首先按照每个物品的单位重量价值从大到小排序，然后依次选择最高价值的物品放入背包中，直到背包已满。如果某个物品不能全部放入背包中，那么只能选择一部分放入。

模拟退火算法求解背包问题python代码

以下是使用模拟退火算法求解背包问题的 Python 代码示例：

import random
import math

# 背包问题求解函数
def knapsack(capacity, weights, values, max_iterations):
    # 初始化当前解和最佳解
    current_solution = [random.randint(0, 1) for i in range(len(weights))]
    best_solution = current_solution[:]
    # 计算当前解的价值和重量
    current_weight = sum([current_solution[i]*weights[i] for i in range(len(weights))])
    current_value = sum([current_solution[i]*values[i] for i in range(len(values))])
    # 初始化温度和降温速率
    temperature = 100
    cooling_rate = 0.03
    # 迭代求解
    for i in range(max_iterations):
        # 生成一个新解
        new_solution = current_solution[:]
        index = random.randint(0, len(weights)-1)
        new_solution[index] = 1 - new_solution[index] # 取反操作
        # 计算新解的价值和重量
        new_weight = sum([new_solution[i]*weights[i] for i in range(len(weights))])
        new_value = sum([new_solution[i]*values[i] for i in range(len(values))])
        # 计算能量差
        delta_e = new_value - current_value
        # 如果新解更优，则接受该解
        if new_weight <= capacity and delta_e > 0:
            current_solution = new_solution[:]
            current_weight = new_weight
            current_value = new_value
            # 更新最佳解
            if current_value > sum([best_solution[i]*values[i] for i in range(len(values))]):
                best_solution = current_solution[:]
        # 如果新解不优，则以一定概率接受该解
        else:
            probability = math.exp(delta_e/temperature)
            if random.random() < probability:
                current_solution = new_solution[:]
                current_weight = new_weight
                current_value = new_value
        # 降温
        temperature *= 1 - cooling_rate
    # 返回最佳解
    return best_solution

# 测试
capacity = 50
weights = [10, 20, 30, 40, 50]
values = [20, 30, 66, 40, 60]
max_iterations = 10000
best_solution = knapsack(capacity, weights, values, max_iterations)
best_weight = sum([best_solution[i]*weights[i] for i in range(len(weights))])
best_value = sum([best_solution[i]*values[i] for i in range(len(values))])
print("最佳解：", best_solution)
print("最佳重量：", best_weight)
print("最佳价值：", best_value)

这段代码中，我们通过模拟退火算法求解背包问题。首先，我们初始化当前解和最佳解为随机解，然后计算当前解的价值和重量。接着，我们初始化温度和降温速率，进行迭代求解。在每次迭代中，我们生成一个新解，计算新解的价值和重量，然后计算能量差。如果新解更优，则接受该解；否则，以一定概率接受该解。最后，我们返回最佳解。