0-1背包

0-1背包（0-1 Knapsack）

有一个小偷带了一个能够装C = 20公斤物品的背包到商店里面偷东西，请问他要怎么偷才能使价值最高？

物品	重量W	价格V
0	2	3
1	3	4
2	4	5
3	5	8
4	9	10

假设用B(k, C)表示当背包容量还剩下C的时候，在前k件物品中能偷到的最大价值。物品从0开始编号，前k件物品的最后一件下标为k - 1。

B(k,C)=\begin{cases} B(k-1,C), & w_{k-1}>C \\ \max\{B(k-1,C), B(k-1,C-w_{k-1})+v_{k-1}\}, & w_{k-1}\le C \end{cases}

边界情况为B(i, 0) = B(0, j) = 0，即当背包容量为0或者没有物品可偷的情况下，最大价值为0。

PRO EXCLUSIVE探索不止于此

解锁完整互动实验、进阶解析与精选参考答案。

尊享 Pro 权益

0-1背包

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct {
    int weight;
    int value;
} Item;

Item item_create(int weight, int value) {
    Item item;
    item.weight = weight;
    item.value = value;
    return item;
}

static int max_int(int a, int b) {
    return a > b ? a : b;
}

int knapsack(Item *items, int n, int capacity) {
    int values[n + 1][capacity + 1];
    memset(values, 0, sizeof(values));

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= capacity; j++) {
            if (items[i - 1].weight > j) {
                values[i][j] = values[i - 1][j];
            } else {
                values[i][j] = max_int(
                    values[i - 1][j - items[i - 1].weight] + items[i - 1].value,
                    values[i - 1][j]
                );
            }
        }
    }

    return values[n][capacity];
}

int main(void) {
    Item items[] = {
        item_create(2, 3),
        item_create(3, 4),
        item_create(4, 5),
        item_create(5, 8),
        item_create(9, 10),
    };
    int n = sizeof(items) / sizeof(Item);
    int capacity = 20;

    printf("%d\n", knapsack(items, n, capacity));
    return 0;
}

物品重量为正整数，价值和背包容量为非负整数；每件物品只能取一次。

题目

取当前物品时，为何读取上一行B(k−1,C−w)？

题目

容量5，物品(重2值3)、(重3值4)，加入第二件后B(2,5)是多少？

物品 0

w=2, v=4

物品 1

w=3, v=5

物品 2

w=4, v=7

容量7，每件物品只取一次。给出每加入一件物品后的容量0—7状态，展示取/不取的依赖，回溯最佳物品组合。

0-1背包（0-1 Knapsack）

有一个小偷带了一个能够装C = 20公斤物品的背包到商店里面偷东西，请问他要怎么偷才能使价值最高？

物品

重量W

价格V

假设用B(k, C)表示当背包容量还剩下C的时候，在前k件物品中能偷到的最大价值。物品从0开始编号，前k件物品的最后一件下标为k - 1。

B(k,C)=\begin{cases} B(k-1,C), & w_{k-1}>C \\ \max\{B(k-1,C), B(k-1,C-w_{k-1})+v_{k-1}\}, & w_{k-1}\le C \end{cases}

边界情况为B(i, 0) = B(0, j) = 0，即当背包容量为0或者没有物品可偷的情况下，最大价值为0。

PRO EXCLUSIVE探索不止于此

解锁完整互动实验、进阶解析与精选参考答案。

尊享 Pro 权益

0-1背包

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct {
    int weight;
    int value;
} Item;

Item item_create(int weight, int value) {
    Item item;
    item.weight = weight;
    item.value = value;
    return item;
}

static int max_int(int a, int b) {
    return a > b ? a : b;
}

int knapsack(Item *items, int n, int capacity) {
    int values[n + 1][capacity + 1];
    memset(values, 0, sizeof(values));

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= capacity; j++) {
            if (items[i - 1].weight > j) {
                values[i][j] = values[i - 1][j];
            } else {
                values[i][j] = max_int(
                    values[i - 1][j - items[i - 1].weight] + items[i - 1].value,
                    values[i - 1][j]
                );
            }
        }
    }

    return values[n][capacity];
}

int main(void) {
    Item items[] = {
        item_create(2, 3),
        item_create(3, 4),
        item_create(4, 5),
        item_create(5, 8),
        item_create(9, 10),
    };
    int n = sizeof(items) / sizeof(Item);
    int capacity = 20;

    printf("%d\n", knapsack(items, n, capacity));
    return 0;
}

物品重量为正整数，价值和背包容量为非负整数；每件物品只能取一次。

题目

取当前物品时，为何读取上一行B(k−1,C−w)？

题目

容量5，物品(重2值3)、(重3值4)，加入第二件后B(2,5)是多少？

物品 0

w=2, v=4

物品 1

w=3, v=5

物品 2

w=4, v=7

容量7，每件物品只取一次。给出每加入一件物品后的容量0—7状态，展示取/不取的依赖，回溯最佳物品组合。

0-1背包（0-1 Knapsack）

0-1背包：取与不取、逐格填表、回溯物品

知识测验

知识测验

比较取与不取并回溯

0-1背包

0-1背包（0-1 Knapsack）

0-1背包：取与不取、逐格填表、回溯物品

知识测验

知识测验

比较取与不取并回溯