当前位置: 面试刷题>> 背包问题Ⅱ (经典算法题500道)


题目描述补充:

背包问题Ⅱ(完全背包问题)

给定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)); // 输出最大值

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

推荐面试题