当前位置：首页 > 行业知识 > 动态规划-01背包问题新解(c)

行业知识

动态规划-01背包问题新解(c)

2026-10-21 16:49:26 来源：互联网转载

动态规划-01背包问题新解

概述
动态规划
01背包问题
传统思路算法
官方递推关系算法

2��算法比较

概述

本文将从一个新的角度来描述和实现01背包问题，以协助对01背包问题以及教材上的算法的彻底理解。

（）

新的角度为：传统思路算法，“新”是新在与绝大部分官方算法思路的区别，但是该算法的思路是传统的，传统是指动态规划领域的传统。

本文的主体结构：

（）

动态规划：简介动态规划问题，因为01背包问题是动态规划中的经典示例之一
01背包问题：01背包问题简介
传统思路算法：区别于“官方”的算法实现，使用传统的动态规划思想来实现01背包问题，以帮助理解01背包问题的基本实现思想
官方递推关系算法：在传统思路算法的基础上，再来理解“官方”算法。

2种算法比较：最后总结01背包问题，比较2种算法

动态规划

动态规划（dynamic programming）是一种算法设计方法。基本思想是在对一个问题的多阶段决策中，按照某一顺序，根据每一步所选决策的不同，会引起状态的转移，最后会在变化的状态中获取到一个决策序列。

上面这段话是比较官方的术语描述，还可以这样从编程层面理解：动态规划一般用于求解具有重叠子问题和最优子结构特性的问题。它通过将大问题分解为小问题，并存储小问题的解（通常在一个表格中），避免了重复计算，从而提高了效率。动态规划可以应用于许多类型的问题，包括但不限于最优化问题、计数问题和决策问题。

01背包问题

01背包问题（0-1 Knapsack Problem）：已知n种物品和一个可容纳c重量的背包，物品i的重量为wi，产生的效益为pi。在装包时物品i可以装入，也可不装入，但不可拆开装。如何装包，所装物品效益最大。

如何理解01背包问题中的01呢？0表示物品不放入背包，1表示物品放入背包。是每个物品放入/不放入背包的状态。

传统思路算法

传统的算法思路：记录每个物品放入和不放入背包的多种排列组合的效益值，取其中最大的效益值。

例如:假设有3个物品，背包最大承重为10，物品的重量分别为(3, 5, 4)，效益分别为(4, 2, 5)。那么就有23=8种放入背包的情况：

序号	组合情况	说明	最大效益
1	0, 0, 0	3个物品都不放入背包	0
2	0, 0, 1	只放入第3个物品	5
3	0, 1, 0	只放入第2个物品	2
4	0, 1, 1	只放入第2、3个物品	7
5	1, 1, 1	3个物品都放入背包	11，但超过背包容量
6	1, 1, 0	放入第1和2个物品	6
7	1, 0, 1	放入第1和3个物品	9，最大的效益
8	1, 0, 0	放入第1个物品	4

从上表可以看出，最终的最大效益为9，放入1和3个物品，此时放入的重量为7。

上述表格构建的过程，就是传统的（典型的）动态规划思路：记录每个过程（每个小问题）的结果，避免重复计算。

这算法思路是最简单，也是最容易理解的。现在用代码来实现这个算法：

构建多维数组，数组每个维度的大小为2。每个维度的索引只有0和1，每个维度的索引对应一个物品，索引为0表示不放入该物品，为1表示放入该物品。例如，上面这个示例中，会构建一个3维数组array，那么array[0][0][1]记录的是只放入第3个物品时的效益。
遍历多维数组，计算每个物品组合的最大效益。注意还要考虑物品重量和不能超过背包容量。
遍历过程中记录最大的效益值和对应的索引，遍历结束后就可以得到最终的解（包括最大效益是多少，物品如何放入背包，放入背包的物品重量和，背包剩余容量）

这个算法的思路很简单，要说有难点的话，可能在多维数组的实现，但是多维数组的实现可以很简单，直接粘贴代码：

多维数组（multidimensional_array.h）

#ifndef __MULTIDIMENSIONAL_ARRAY_H__#define __MULTIDIMENSIONAL_ARRAY_H__/** * 多维数组的C实现 */typedef unsigned long long u64;typedef long long s64;typedef unsigned int u32;typedef struct _MultiDimArray {    int *data;    int dimensions;    int *sizes;    int total_size;} multi_dim_array;// 创建多维数组multi_dim_array *create_multi_dim_array(int dim, int *sizes);// 释放多维数组void free_multi_dim_array(multi_dim_array *array);// 多维索引转一维索引int indices_to_index(multi_dim_array *array, int *indices);// 一维索引转多维索引: 记得用完释放内存int *index_to_indices(multi_dim_array *array, int index);// 设置多维数组的值void set_value_at(multi_dim_array *array, int *indices, int value);typedef u64 (*md_arr_item_proc_fn)(multi_dim_array *array, int *indices, int index, int val, void *context);// 遍历多维数组void traverse_multi_dim_array(multi_dim_array *array, md_arr_item_proc_fn proc, void *context);#endif  // __MULTIDIMENSIONAL_ARRAY_H__

多维数组（multidimensional_array.c）

#include "multidimensional_array.h"#include #include multi_dim_array *create_multi_dim_array(int dim, int *sizes) {    multi_dim_array *array = (multi_dim_array *)malloc(sizeof(multi_dim_array));    array->dimensions = dim;    array->sizes = (int *)malloc(dim * sizeof(int));    int totalSize = 1;    for (int i = 0; i sizes[i] = sizes[i];        if (sizes[i]             return NULL;        }        totalSize *= sizes[i];    }    array-total_size = totalSize;    array->data = (int *)malloc(sizeof(int) * totalSize);    memset(array->data, 0x0, sizeof(int) * totalSize);    return array;}void free_multi_dim_array(multi_dim_array *array) {    free(array->sizes);    array->sizes = NULL;    free(array->data);    array->data = NULL;    array->dimensions = 0;    array->total_size = 0;    free(array);}int indices_to_index(multi_dim_array *array, int *indices) {    int index = 0, multiplier = 1;    for (int i = array->dimensions - 1; i >= 0; i--) {        index += indices[i] * multiplier;        if (i > 0) {            multiplier *= array->sizes[i];        }    }    return index;}int *index_to_indices(multi_dim_array *array, int index) {    int *indices = (int *)malloc(sizeof(int) * array->dimensions);    for (int i = array->dimensions - 1; i >= 0; i--) {        if (i == 0) {            // 对于最外层，直接将剩余的index赋值            indices[i] = index;        } else {            indices[i] = index % array->sizes[i];            index /= array->sizes[i];        }    }    return indices;}void set_value_at(multi_dim_array *array, int *indices, int value) {    int index = indices_to_index(array, indices);    array->data[index] = value;}void traverse_multi_dim_array(multi_dim_array *array, md_arr_item_proc_fn proc, void *context) {    if (proc == NULL) {        return;    }    int *skip_prefix = NULL, skip_len = 0;    for (int index = 0; index total_size; index++) {        int *indices = index_to_indices(array, index);        if (skip_prefix != NULL) {            if (memcmp(indices, skip_prefix, skip_len * sizeof(int)) == 0) {                free(indices);                continue;            }            free(skip_prefix);            skip_prefix = NULL;            skip_len = 0;        }        u64 ret = proc(array, indices, index, array->data[index], context);        if (ret == (u64)-1) {            free(indices);            if (skip_prefix != NULL) {                free(skip_prefix);            }            return;        }        if (ret != 0) {            skip_prefix = (int *)ret;            skip_len = skip_prefix[array->dimensions];        }        free(indices);    }    if (skip_prefix != NULL) {        free(skip_prefix);    }}

01背包问题（01KnapsackProblem.h）

inline int max(int a, int b) {    return (a > b) ? a : b;}// 01背包问题的结果定义typedef struct _01KpResult {    int p;         // 总的效益    int w;         // 放入的总重量    int length;    // 数组长度    int select[];  // 物品放入背包的状态: 0 - 不放入; 1 - 放入} dp_01_kp_result;/** * @brief 动态规划-01背包问题: 常规（传统）思路，使用多维数组记录每种物品放与不放的效益，找最大值。该方法更容易理解，但是当物品数量增加时，复杂度指数级增加(2为底的指数级增加)， * * @param n n种物品 * @param c 背包容量（重量） * @param w 物品的重量（数组） * @param p 物品的效益（数组） * @param times 与算法无关，用于统计遍历次数 * @return dp_01_kp_result* 结果 */dp_01_kp_result* dp_01_knapsack_problem_general_way(int n, int c, int w[], int p[], long* times);

01背包问题（01KnapsackProblem.c）

// 采用常规思路的方法typedef struct _kp_context {    int n;    int c;    int *w;    int *p;    int max_p;    int index;    long *times;} kp_context;u64 proc_each_step(multi_dim_array *array, int *indices, int index, int val, void *context) {    kp_context *kc = (kp_context *)context;    int weight = 0, p_val = 0;    for (int i = 0; i dimensions; i++) {        (*kc->times)++;        if (indices[i] != 0) {            // 放            weight += kc->w[i];            if (weight > kc->c) {                int *skip_prefix = (int *)malloc((array->dimensions + 1) * sizeof(int));                memcpy(skip_prefix, indices, (i + 1) * sizeof(int));                skip_prefix[array->dimensions] = i + 1;                return (u64)skip_prefix;            }            p_val += kc->p[i];        }    }    if (kc->max_p max_p = p_val;        kc->index = index;    }    return 0;}dp_01_kp_result *dp_01_knapsack_problem_general_way(int n, int c, int w[], int p[], long *times) {    int *array_sizes = (int *)malloc(sizeof(int) * n);    for (int i = 0; i p = kc.max_p;    result->length = n;    // printf("** kc index[%d] max_p[%d]\n", kc.index, kc.max_p);    (*times) += 2 * n;    int *indices = index_to_indices(array, kc.index);    for (int i = 0; i select[i] = indices[i];        if (indices[i] == 1) {            result->w += w[i];        }    }    free(indices);    free_multi_dim_array(array);    return result;}

测试代码（test_01_kp.c）

void print_result(int caseId, dp_01_kp_result *result, long times, int leftW) {    printf("case[%02d] total: %d, leftW: %2d, times: %5ld, select: ", caseId, result->p, leftW, times);    for (int i = 0; i length; i++) {        printf("%d", result->select[i]);        if (i != result->length - 1) {            printf(", ");        }    }    printf("\n");}int test_01_kp(int argc, char **argv) {    kp_param params[] = {        kp_param{            n : 6,            c : 60,            w : {15, 17, 20, 12, 9, 14},            p : {32, 37, 46, 26, 21, 30},        },        kp_param{            n : 3,            c : 50,            w : {10, 20, 30},            p : {60, 100, 120},        },        kp_param{            n : 10,            c : 100,            w : {15, 17, 20, 12, 9, 14, 11, 23, 60, 50},            p : {32, 37, 46, 26, 21, 30, 30, 20, 50, 40},        },        kp_param{            n : 10,            c : 100,            w : {23, 60, 50, 15, 17, 20, 12, 9, 14, 11},            p : {20, 50, 40, 32, 37, 46, 26, 21, 30, 30},        },        kp_param{            // 法2优于法1一点点            n : 10,            c : 1000,            w : {23, 60, 50, 15, 17, 20, 12, 9, 14, 11},            p : {20, 50, 40, 32, 37, 46, 26, 21, 30, 30},        },        kp_param{            n : 10,            c : 220,            w : {23, 60, 50, 15, 17, 20, 12, 9, 14, 11},            p : {20, 50, 40, 32, 37, 46, 26, 21, 30, 30},        },    };    int len = sizeof(params) / sizeof(params[0]);    long times = 0;    for (int i = 0; i n, param->c, param->w, param->p, &times);        if (result == NULL) {            return -1;        }        print_result(i + 1, result, times, param->c - result->w);        free(result);        times = 0;    }    return 0;}

测试输出：

case[01] total: 134, leftW: 0, times: 432, select: 0, 1, 1, 0, 1, 1

case[02] total: 220, leftW: 0, times: 206, select: 0, 1, 1

case[03] total: 222, leftW: 2, times: 1121, select: 1, 1, 1, 1, 1, 1, 1, 0, 0, 0

case[04] total: 222, leftW: 2, times: 1121, select: 0, 0, 0, 1, 1, 1, 1, 1, 1, 1

case[05] total: 332, leftW: 769, times: 11021, select: 1, 1, 1, 1, 1, 1, 1, 1, 1, 1

case[06] total: 312, leftW: 12, times: 2441, select: 0, 1, 1, 1, 1, 1, 1, 1, 1, 1

接下来描述“官方”的算法和实现，以便后续与本算法进行对比。

官方递推关系算法

基本上所有的01背包问题，都是采用的这个递推关系：

设m(i, j)为背包容量j，可取物品范围为i~n的最大效益值。则

当0 = wi时，有两种选择:

(1) 不装入物品i，这时的最大效益值与m(i+1, j)相同;

(2) 装入物品i，这时会产生效益pi，背包剩余容量为j - wi，可以选择物品i+1 ~ n来装，最大效益值为m(i+1, j-wi) + pi;

取这两种情况中的最大值的那个max(m(i+1, j), m(i+1, j-wi) + pi)

该递推关系从物品选择和背包容量2个角度来递推的，算法过程中使用二维数组记录每种i和j的配对情况下的效益值，最终的结果为m(1, c)。

为了方便编码，同等地可将上面这个递推关系调整为（上面是逆序的，下面改为顺序的遍历）：

设m(i, j)为背包容量j，可取物品范围为1, 2, …, i的最大效益值。则

当0 = wi时，有两种选择:

(1) 不装入物品i，这时的最大效益值与m(i-1, j)相同;

(2) 装入物品i，这时会产生效益p(i)，背包剩余容量为j - wi，可以选择物品1, 2, …, i-1来装，最大效益值为m(i-1, j-wi) + pi;

取这两种情况中的最大值的那个max(m(i-1, j), m(i-1, j-wi) + pi)

调整后的递推关系，最终结果为m(n, c)。

代码实现