题目描述补充：

背包问题Ⅱ（完全背包问题）

给定n种物品和一个容量为W的背包。物品i的重量是weight[i]，其价值为value[i]，每种物品都有无限件可用。问应如何选择装入背包的物品，使得背包内物品的总价值最大？

注意：这与01背包问题的主要区别在于每种物品可以取无限次，而不仅仅是0次或1次。

示例

假设有4种物品和一个容量为10的背包，物品的重量和价值如下：

• 物品1：重量2，价值6
• 物品2：重量2，价值10
• 物品3：重量3，价值12
• 物品4：重量5，价值18

求解这个问题，即找出能装入背包中的物品组合，使得总价值最大。

PHP 代码示例

function knapsackII($W, $weights, $values) {
    $n = count($values);
    $dp = array_fill(0, $W + 1, 0);

    for ($i = 0; $i < $n; $i++) {
        for ($w = $weights[$i]; $w <= $W; $w++) {
            $dp[$w] = max($dp[$w], $dp[$w - $weights[$i]] + $values[$i]);
        }
    }

    return $dp[$W];
}

// 使用示例
$W = 10;
$weights = [2, 2, 3, 5];
$values = [6, 10, 12, 18];
echo knapsackII($W, $weights, $values); // 输出最大值

Python 代码示例

def knapsackII(W, weights, values):
    dp = [0] * (W + 1)
    n = len(values)

    for i in range(n):
        for w in range(weights[i], W + 1):
            dp[w] = max(dp[w], dp[w - weights[i]] + values[i])

    return dp[W]

# 使用示例
W = 10
weights = [2, 2, 3, 5]
values = [6, 10, 12, 18]
print(knapsackII(W, weights, values))  # 输出最大值

JavaScript 代码示例

function knapsackII(W, weights, values) {
    let dp = new Array(W + 1).fill(0);
    const n = values.length;

    for (let i = 0; i < n; i++) {
        for (let w = weights[i]; w <= W; w++) {
            dp[w] = Math.max(dp[w], dp[w - weights[i]] + values[i]);
        }
    }

    return dp[W];
}

// 使用示例
const W = 10;
const weights = [2, 2, 3, 5];
const values = [6, 10, 12, 18];
console.log(knapsackII(W, weights, values)); // 输出最大值

码小课 网站中有更多关于算法和数据结构的相关内容，包括但不限于背包问题的详细讲解和进阶应用，欢迎大家访问学习。