30804：0/1 背包

题目

每件物品至多选择一次，在容量不超过 capacity 的前提下最大化总价值。

解析

dp[c] 表示处理完当前前缀物品后、容量不超过 c 时的最大价值。处理一件物品时从大容量向小容量更新，右侧状态仍是上一轮的值，因此零重量物品也只会被使用一次。

答案

#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>
#include <stdlib.h>

bool knapsack_01(
    const size_t *weights,
    const uint64_t *values,
    size_t count,
    size_t capacity,
    uint64_t *out_value
) {
    if (out_value == NULL ||
        (count > 0 && (weights == NULL || values == NULL)) ||
        capacity == SIZE_MAX ||
        capacity + 1 > SIZE_MAX / sizeof(uint64_t)) {
        return false;
    }
    uint64_t *dp = calloc(capacity + 1, sizeof *dp);
    if (dp == NULL) {
        return false;
    }
    for (size_t item = 0; item < count; ++item) {
        if (weights[item] > capacity) {
            continue;
        }
        size_t c = capacity;
        for (;;) {
            if (dp[c - weights[item]] >
                UINT64_MAX - values[item]) {
                free(dp);
                return false;
            }
            uint64_t candidate =
                dp[c - weights[item]] + values[item];
            if (candidate > dp[c]) {
                dp[c] = candidate;
            }
            if (c == weights[item]) {
                break;
            }
            --c;
        }
    }
    *out_value = dp[capacity];
    free(dp);
    return true;
}

状态数组为 $O(C)$，每件物品最多访问 $C+1$ 个容量，时间复杂度为 $O(nC)$。