1. AI技术聚合首页
  2. IT

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

乘风 • • IT • 阅读 15

动态规划-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。
上述表格构建的过程，就是传统的（典型的）动态规划思路：记录每个过程（每个小问题）的结果，避免重复计算。
这算法思路是最简单，也是最容易理解的。现在用代码来实现这个算法：

  1. 构建多维数组，数组每个维度的大小为2。每个维度的索引只有0和1，每个维度的索引对应一个物品，索引为0表示不放入该物品，为1表示放入该物品。例如，上面这个示例中，会构建一个3维数组array，那么array[0][0][1]记录的是只放入第3个物品时的效益。
  2. 遍历多维数组，计算每个物品组合的最大效益。注意还要考虑物品重量和不能超过背包容量。
  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 <stdlib.h>
#include <string.h>

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 < dim; i++) {
        array->sizes[i] = sizes[i];
        if (sizes[i] <= 0) {
            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 < array->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 < array->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 < p_val) {
        kc->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 < n; i++) {
        array_sizes[i] = 2;  // 每个维度只有2个，下标0表示不放，1表示放
    }
    kp_context kc = {
        n : n,
        c : c,
        w : &w[0],
        p : &p[0],
        max_p : 0,
        index : 0,
        times : times,
    };
    // 创建一个n维的多维数组
    multi_dim_array *array = create_multi_dim_array(n, array_sizes);
    free(array_sizes);
    array_sizes = NULL;
    // 遍历多维数组来对比每一种物品组合的最大效益
    traverse_multi_dim_array(array, proc_each_step, (void *)&kc);
    // 构造结果
    dp_01_kp_result *result = (dp_01_kp_result *)malloc(sizeof(dp_01_kp_result) + sizeof(int) * n);
    memset(result, 0x0, sizeof(dp_01_kp_result) + sizeof(int) * n);
    result->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 < n; i++) {
        result->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 < result->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 < len; i++) {
        kp_param *param = &params[i];
        dp_01_kp_result *result = dp_01_knapsack_problem_general_way(param->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 <= j < wi时，物品i不可能装入，最大效益值与m(i+1, j)相同;
  • 当j >= 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 <= j < wi时，物品i不可能装入，最大效益值与m(i-1, j)相同;
  • 当j >= 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)。

代码实现
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背包问题: 二维数组记录递归中间结果，递推关系使用的是放的物品和背包容量
 *
 * @param n n种物品
 * @param c 背包容量（重量）
 * @param w 物品的重量（数组）
 * @param p 物品的效益（数组）
 * @return dp_01_kp_result* 结果
 */
dp_01_kp_result* dp_01_knapsack_problem(int n, int c, int w[], int p[], long* times);

01背包问题（01KnapsackProblem.c）

dp_01_kp_result *dp_01_knapsack_problem(
    int n,       // 物品种类数量
    int c,       // 背包重量容量
    int w[],     // 每个物品的重量
    int p[],     // 每个物品的效益
    long *times  // 遍历次数统计
) {
    int dp[n + 1][c + 1];  // dp[i][j]表示，背包容量为j，可取物品访问为1～i的最大效益值
    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= c; j++) {
            (*times)++;
            if (i == 0 || w == 0) {
                dp[i][j] = 0;
            } else if (w[i - 1] <= j) {
                // 当 j >= w[i]（由于0被占用，这里取的是w[i-1]）
                // 分2种情况：
                // 1) 放入i：p[i - 1] + dp[i - 1][j - w[i - 1]]
                //    其中p[i - 1]是i物品的效益，dp[i - 1][j - w[i - 1]]是为i预留空间时的i-1物品的最大效益
                // 2) 不放入i: dp[i - 1][j]
                // 取二者最大值
                dp[i][j] = max(p[i - 1] + dp[i - 1][j - w[i - 1]], dp[i - 1][j]);
            } else {
                // 当 j < w[i] （由于0被占用，这里取的是w[i-1]）
                // 说明不放入i，那么就有：
                dp[i][j] = dp[i - 1][j];
            }
        }
    }
    dp_01_kp_result *result = (dp_01_kp_result *)malloc(sizeof(dp_01_kp_result) + sizeof(int) * n);
    memset(result, 0x0, sizeof(dp_01_kp_result) + sizeof(int) * n);
    result->p = dp[n][c];
    result->length = n;
    // 方向找到选择了哪些物品
    for (int i = n; i > 0 && c > 0; i--) {
        (*times)++;
        if (dp[i][c] != dp[i - 1][c]) {
            // 说明放入了i-1
            result->select[i - 1] = 1;  // 标记选择
            c -= w[i - 1];
            result->w += w[i - 1];
        }
    }
    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 < result->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 < len; i++) {
        kp_param *param = &params[i];
        dp_01_kp_result *result = dp_01_knapsack_problem(param->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

2种算法比较

  • 算法1简单易懂，算法2会比较难懂。算法2很难理解的点为：为什么按照物品i的选择和背包容量j这2个维度来构建递推关系

  • 算法2优于算法1
    (1) 算法1时间复杂度为2n,其中n是物品的个数，随着物品的数量增加，复杂度指数级递增；
    (2) 算法2时间复杂度为n*c，其中n为物品的数量，c是背包的容量。
    上面的测试结果，汇总如下，其中每组输出中带”–>”开头的是算法1的结果：

case[01] total: 134, leftW:     0, times:    432, select: 0, 1, 1, 0, 1, 1
         –> total: 134, leftW:     0, times:    369, select: 0, 1, 1, 0, 1, 1
case[02] total: 220, leftW:     0, times:    206, select: 0, 1, 1
         –> total: 220, leftW:     0, times:      30, select: 0, 1, 1
case[03] total: 222, leftW:     2, times:   1121, select: 1, 1, 1, 1, 1, 1, 1, 0, 0, 0
         –> total: 222, leftW:     2, times:   7805, 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
         –> total: 222, leftW:     2, times:   4762, 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
         –> total: 332, leftW: 769, times: 10260, 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
         –> total: 312, leftW:   12, times: 10260, select: 0, 1, 1, 1, 1, 1, 1, 1, 1, 1

可以看到在n比较小的时候，算法1优于算法2；当随着n的增大，算法2的优势就体现出来了。

  • 算法1帮助理解算法2。算法1很容易理解，但是当n足够大时，复杂度指数增长，那么如何优化呢？于是前辈们就折腾出了算法2，不得不让人佩服。

20240324补充：
点击查看源代码，代码目录:

  • multidimensional_array 多维数组
  • 01_knapsack 01背包代码

运行测试：关注README.md中“运行测试”第5条“01 背包问题(01 knapsack problem)”。

版权声明：本文为博主作者：丑井原创文章，版权归属原作者，如果侵权，请联系我们删除！

原文链接：https://blog.csdn.net/songqier/article/details/136225134

共计人评分，平均分

到目前为止还没有投票！成为第一位评论此文章。

赞 (0)
乘风的头像乘风管理团队
0
上一篇 2024年4月22日
下一篇 2024年4月22日

相关推荐