Задача о рюкзаке (Knapsack)
0/1 Knapsack
Условие: есть n предметов с весами и ценностями. Рюкзак вмещает W. Каждый предмет можно взять максимум один раз. Максимизировать ценность.
Предметы: [(вес=1, цена=6), (вес=2, цена=10), (вес=3, цена=12)]
Рюкзак: W = 5
Оптимально: предмет 1 + предмет 2 = вес 3, цена 16
Или: предмет 1 + предмет 3 = вес 4, цена 18 <- лучше!
Или: предмет 2 + предмет 3 = вес 5, цена 22 <- оптимум!
Рекуррентность
dp[i][w] = макс. ценность, используя первые i предметов с ёмкостью w
dp[i][w] = max(
dp[i-1][w], # Не берём предмет i
dp[i-1][w - weight[i]] + value[i] # Берём предмет i (если влезает)
)
Реализация 2D
PHPGo
<?php
declare(strict_types=1);
/**
* @param list<int> $weights
* @param list<int> $values
*/
function knapsack01(array $weights, array $values, int $W): int
{
$n = count($weights);
$dp = array_fill(0, $n + 1, array_fill(0, $W + 1, 0));
for ($i = 1; $i <= $n; $i++) {
for ($w = 0; $w <= $W; $w++) {
$dp[$i][$w] = $dp[$i - 1][$w]; // Skip item
if ($weights[$i - 1] <= $w) {
$dp[$i][$w] = max(
$dp[$i][$w],
$dp[$i - 1][$w - $weights[$i - 1]] + $values[$i - 1]
);
}
}
}
return $dp[$n][$W];
}
// weights = [1, 2, 3], values = [6, 10, 12], W = 5
// Answer: 22
package main
func knapsack01(weights, values []int, W int) int {
n := len(weights)
dp := make([][]int, n+1)
for i := range dp {
dp[i] = make([]int, W+1)
}
for i := 1; i <= n; i++ {
for w := 0; w <= W; w++ {
dp[i][w] = dp[i-1][w] // Skip item
if weights[i-1] <= w {
dp[i][w] = max(
dp[i][w],
dp[i-1][w-weights[i-1]]+values[i-1],
)
}
}
}
return dp[n][W]
}
// weights = [1, 2, 3], values = [6, 10, 12], W = 5
// Answer: 22
w=0 w=1 w=2 w=3 w=4 w=5
i=0 (-) 0 0 0 0 0 0
i=1 (1,6) 0 6 6 6 6 6
i=2 (2,10)0 6 10 16 16 16
i=3 (3,12)0 6 10 16 18 22
^
ответ
Оптимизация до 1D
Заполняем справа налево чтобы не использовать обновлённые значения текущей строки.
PHPGo
<?php
declare(strict_types=1);
/**
* @param list<int> $weights
* @param list<int> $values
*/
function knapsack01Optimized(array $weights, array $values, int $W): int
{
$dp = array_fill(0, $W + 1, 0);
for ($i = 0; $i < count($weights); $i++) {
for ($w = $W; $w >= $weights[$i]; $w--) { // Right to left!
$dp[$w] = max($dp[$w], $dp[$w - $weights[$i]] + $values[$i]);
}
}
return $dp[$W];
}
package main
func knapsack01Optimized(weights, values []int, W int) int {
dp := make([]int, W+1)
for i := 0; i < len(weights); i++ {
for w := W; w >= weights[i]; w-- { // Right to left!
dp[w] = max(dp[w], dp[w-weights[i]]+values[i])
}
}
return dp[W]
}
Отличие: каждый предмет можно брать неограниченное количество раз.
PHPGo
<?php
declare(strict_types=1);
/**
* @param list<int> $weights
* @param list<int> $values
*/
function knapsackUnbounded(array $weights, array $values, int $W): int
{
$dp = array_fill(0, $W + 1, 0);
for ($w = 1; $w <= $W; $w++) {
for ($i = 0; $i < count($weights); $i++) {
if ($weights[$i] <= $w) {
$dp[$w] = max($dp[$w], $dp[$w - $weights[$i]] + $values[$i]);
}
}
}
return $dp[$W];
}
package main
func knapsackUnbounded(weights, values []int, W int) int {
dp := make([]int, W+1)
for w := 1; w <= W; w++ {
for i := 0; i < len(weights); i++ {
if weights[i] <= w {
dp[w] = max(dp[w], dp[w-weights[i]]+values[i])
}
}
}
return dp[W]
}
Задача: Partition Equal Subset Sum
Условие: можно ли разделить массив на две части с равными суммами?
Это 0/1 knapsack: можем ли набрать сумму total/2?
PHPGo
<?php
declare(strict_types=1);
/**
* @param list<int> $nums
*/
function canPartition(array $nums): bool
{
$total = array_sum($nums);
if ($total % 2 !== 0) {
return false;
}
$target = intdiv($total, 2);
$dp = array_fill(0, $target + 1, false);
$dp[0] = true;
foreach ($nums as $num) {
for ($t = $target; $t >= $num; $t--) { // Right to left (0/1)
$dp[$t] = $dp[$t] || $dp[$t - $num];
}
}
return $dp[$target];
}
// nums = [1, 5, 11, 5]
// total = 22, target = 11
// dp after 1: [T, T, F, F, F, F, F, F, F, F, F, F]
// dp after 5: [T, T, F, F, F, T, T, F, F, F, F, F]
// dp after 11:[T, T, F, F, F, T, T, F, F, F, F, T]
// dp[11] = true -> possible (11 and 1+5+5)
package main
func canPartition(nums []int) bool {
total := 0
for _, n := range nums {
total += n
}
if total%2 != 0 {
return false
}
target := total / 2
dp := make([]bool, target+1)
dp[0] = true
for _, num := range nums {
for t := target; t >= num; t-- { // Right to left (0/1)
dp[t] = dp[t] || dp[t-num]
}
}
return dp[target]
}
// nums = [1, 5, 11, 5]
// total = 22, target = 11
// dp after 1: [T, T, F, F, F, F, F, F, F, F, F, F]
// dp after 5: [T, T, F, F, F, T, T, F, F, F, F, F]
// dp after 11:[T, T, F, F, F, T, T, F, F, F, F, T]
// dp[11] = true -> possible (11 and 1+5+5)
Условие: сколько способов набрать сумму amount из данных монет?
PHPGo
<?php
declare(strict_types=1);
/**
* @param list<int> $coins
*/
function change(int $amount, array $coins): int
{
$dp = array_fill(0, $amount + 1, 0);
$dp[0] = 1;
foreach ($coins as $coin) { // For each coin
for ($a = $coin; $a <= $amount; $a++) { // Left to right (unbounded)
$dp[$a] += $dp[$a - $coin];
}
}
return $dp[$amount];
}
// amount = 5, coins = [1, 2, 5]
// Answer: 4 ways
// 5 = 5
// 5 = 2+2+1
// 5 = 2+1+1+1
// 5 = 1+1+1+1+1
package main
func change(amount int, coins []int) int {
dp := make([]int, amount+1)
dp[0] = 1
for _, coin := range coins { // For each coin
for a := coin; a <= amount; a++ { // Left to right (unbounded)
dp[a] += dp[a-coin]
}
}
return dp[amount]
}
// amount = 5, coins = [1, 2, 5]
// Answer: 4 ways
// 5 = 5
// 5 = 2+2+1
// 5 = 2+1+1+1
// 5 = 1+1+1+1+1
Условие: массив чисел, нужно поставить + или - перед каждым, чтобы получить target.
PHPGo
<?php
declare(strict_types=1);
/**
* @param list<int> $nums
*/
function findTargetSumWays(array $nums, int $target): int
{
$total = array_sum($nums);
if (($total + $target) % 2 !== 0 || abs($target) > $total) {
return 0;
}
// Reduces to subset with sum (total + target) / 2
$subsetSum = intdiv($total + $target, 2);
$dp = array_fill(0, $subsetSum + 1, 0);
$dp[0] = 1;
foreach ($nums as $num) {
for ($s = $subsetSum; $s >= $num; $s--) {
$dp[$s] += $dp[$s - $num];
}
}
return $dp[$subsetSum];
}
package main
func findTargetSumWays(nums []int, target int) int {
total := 0
for _, n := range nums {
total += n
}
if (total+target)%2 != 0 || abs(target) > total {
return 0
}
// Reduces to subset with sum (total + target) / 2
subsetSum := (total + target) / 2
dp := make([]int, subsetSum+1)
dp[0] = 1
for _, num := range nums {
for s := subsetSum; s >= num; s-- {
dp[s] += dp[s-num]
}
}
return dp[subsetSum]
}
func abs(x int) int {
if x < 0 {
return -x
}
return x
}
| Тип | Направление цикла | Предмет |
|---|---|---|
| 0/1 Knapsack | Справа налево | Один раз |
| Unbounded | Слева направо | Неограниченно |
| Count ways | += вместо max | Количество способов |
| Subset Sum | bool OR | Можно ли набрать? |
PHPGo
<?php
declare(strict_types=1);
// Template: 0/1 (max value)
foreach ($items as $i) {
for ($w = $W; $w >= $weight[$i]; $w--) { // <-- right to left
$dp[$w] = max($dp[$w], $dp[$w - $weight[$i]] + $value[$i]);
}
}
// Template: Unbounded (max value)
for ($w = 1; $w <= $W; $w++) {
foreach ($items as $i) { // <-- left to right
if ($weight[$i] <= $w) {
$dp[$w] = max($dp[$w], $dp[$w - $weight[$i]] + $value[$i]);
}
}
}
// Template: Count (number of ways)
foreach ($coins as $coin) {
for ($a = $coin; $a <= $amount; $a++) { // <-- left to right
$dp[$a] += $dp[$a - $coin];
}
}
// Template: 0/1 (max value)
for _, i := range items {
for w := W; w >= weight[i]; w-- { // <-- right to left
dp[w] = max(dp[w], dp[w-weight[i]]+value[i])
}
}
// Template: Unbounded (max value)
for w := 1; w <= W; w++ {
for _, i := range items { // <-- left to right
if weight[i] <= w {
dp[w] = max(dp[w], dp[w-weight[i]]+value[i])
}
}
}
// Template: Count (number of ways)
for _, coin := range coins {
for a := coin; a <= amount; a++ { // <-- left to right
dp[a] += dp[a-coin]
}
}
Итоги
- 0/1 Knapsack: dp[w] = max(dp[w], dp[w-wt]+val), обход W..wt
- Unbounded: обход wt..W (слева направо)
- Partition Subset = knapsack с boolean dp
- Coin Change 2 = unbounded с подсчётом (+=)
- 1D оптимизация: направление цикла критически важно