当前位置： 面试刷题>> 背包问题Ⅰ (经典算法题500道)
### 背包问题Ⅰ 题目描述
背包问题（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 代码示例
```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 代码示例
```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 代码示例
```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
```
**码小课**：在码小课网站中，您可以找到更多关于背包问题及其变体的深入解析和代码实现，帮助您更好地理解这类问题并提升编程技能。