当前位置： 面试刷题>> 背包问题Ⅱ (经典算法题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 代码示例
```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 代码示例
```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 代码示例
```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)); // 输出最大值
```
**码小课** 网站中有更多关于算法和数据结构的相关内容，包括但不限于背包问题的详细讲解和进阶应用，欢迎大家访问学习。