背包问题Ⅰ 题目描述

背包问题（Knapsack Problem）是组合优化中的一个经典问题，在给定一组物品，每种物品都有自己的重量和价值，在限定的总重量内，我们如何选择物品装入背包，使得背包内物品的总价值最大。背包问题Ⅰ通常指的是0-1背包问题，即每种物品只能选择装入背包或不装入背包。

具体题目描述： 给定n种物品和一个容量为W的背包。物品i的重量是wt[i]，其价值为val[i]。求解将哪些物品装入背包可使这些物品的总重量不超过背包容量，且总价值最大。

示例

假设有4种物品和一个容量为10的背包。

• 物品的重量：wt = [2, 3, 4, 5]
• 物品的价值：val = [3, 4, 5, 6]
• 背包的最大容量：W = 10

PHP 代码示例

function knapsack($W, $wt, $val, $n) {
    $dp = array_fill(0, $n + 1, array_fill(0, $W + 1, 0));

    for ($i = 1; $i <= $n; $i++) {
        for ($w = 1; $w <= $W; $w++) {
            if ($wt[$i - 1] <= $w) {
                $dp[$i][$w] = max($dp[$i - 1][$w], $dp[$i - 1][$w - $wt[$i - 1]] + $val[$i - 1]);
            } else {
                $dp[$i][$w] = $dp[$i - 1][$w];
            }
        }
    }

    return $dp[$n][$W];
}

// 测试
$val = [3, 4, 5, 6];
$wt = [2, 3, 4, 5];
$W = 10;
$n = count($val);
echo knapsack($W, $wt, $val, $n);  // 输出：10

Python 代码示例

def knapsack(W, wt, val, n):
    dp = [[0 for x in range(W + 1)] for x in range(n + 1)]

    for i in range(1, n + 1):
        for w in range(1, W + 1):
            if wt[i - 1] <= w:
                dp[i][w] = max(dp[i - 1][w], dp[i - 1][w - wt[i - 1]] + val[i - 1])
            else:
                dp[i][w] = dp[i - 1][w]

    return dp[n][W]

# 测试
val = [3, 4, 5, 6]
wt = [2, 3, 4, 5]
W = 10
n = len(val)
print(knapsack(W, wt, val, n))  # 输出：10

JavaScript 代码示例

function knapsack(W, wt, val, n) {
    const dp = Array.from({ length: n + 1 }, () => Array(W + 1).fill(0));

    for (let i = 1; i <= n; i++) {
        for (let w = 1; w <= W; w++) {
            if (wt[i - 1] <= w) {
                dp[i][w] = Math.max(dp[i - 1][w], dp[i - 1][w - wt[i - 1]] + val[i - 1]);
            } else {
                dp[i][w] = dp[i - 1][w];
            }
        }
    }

    return dp[n][W];
}

// 测试
const val = [3, 4, 5, 6];
const wt = [2, 3, 4, 5];
const W = 10;
const n = val.length;
console.log(knapsack(W, wt, val, n));  // 输出：10

码小课：在码小课网站中，您可以找到更多关于背包问题及其变体的深入解析和代码实现，帮助您更好地理解这类问题并提升编程技能。