四川建设集团有限公司网站,wordpress页面结构,做网站茶叶首页标题怎么写,深圳设计学院动态规划-01背包问题新解 概述动态规划01背包问题传统思路算法官方递推关系算法2种算法比较 概述
本文将从一个新的角度来描述和实现01背包问题#xff0c;以协助对01背包问题以及教材上的算法的彻底理解。
新的角度为#xff1a;传统思路算法#xff0c;“新”是新在与绝… 动态规划-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)。那么就有238种放入背包的情况
序号组合情况说明最大效益10, 0, 03个物品都不放入背包020, 0, 1只放入第3个物品530, 1, 0只放入第2个物品240, 1, 1只放入第2、3个物品751, 1, 13个物品都放入背包11但超过背包容量61, 1, 0放入第1和2个物品671, 0, 1放入第1和3个物品9最大的效益81, 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 stdlib.h
#include string.hmulti_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 result1-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(i1, j)相同;当j wi时有两种选择: (1) 不装入物品i这时的最大效益值与m(i1, j)相同; (2) 装入物品i这时会产生效益pi背包剩余容量为j - wi可以选择物品i1 ~ n来装最大效益值为m(i1, j-wi) pi; 取这两种情况中的最大值的那个max(m(i1, j), m(i1, 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可取物品访问为1i的最大效益值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) 放入ip[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-1result-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 result1-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 (result1 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不得不让人佩服。
