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

2024-02-28 12:20
文章标签 动态 规划 问题 01 背包 新解

本文主要是介绍动态规划-01背包问题新解(c)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

动态规划-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种放入背包的情况：

序号组合情况说明最大效益
10, 0, 03个物品都不放入背包0
20, 0, 1只放入第3个物品5
30, 1, 0只放入第2个物品2
40, 1, 1只放入第2、3个物品7
51, 1, 13个物品都放入背包11，但超过背包容量
61, 1, 0放入第1和2个物品6
71, 0, 1放入第1和3个物品9，最大的效益
81, 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 < 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(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-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，不得不让人佩服。

这篇关于动态规划-01背包问题新解(c)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/755498。

相关文章

好题——hdu2522（小数问题：求1/n的第一个循环节）

好题——hdu2522（小数问题：求1/n的第一个循环节）

好喜欢这题，第一次做小数问题，一开始真心没思路，然后参考了网上的一些资料。 知识点***********************************无限不循环小数即无理数，不能写作两整数之比*****************************（一开始没想到，小学没学好） 此题1/n肯定是一个有限循环小数，了解这些后就能做此题了。 按照除法的机制，用一个函数表示出来就可以了，代码如下
阅读更多...
hdu1043（八数码问题，广搜 + hash（实现状态压缩） ）

hdu1043（八数码问题，广搜 + hash（实现状态压缩） ）

利用康拓展开将一个排列映射成一个自然数，然后就变成了普通的广搜题。 #include<iostream>#include<algorithm>#include<string>#include<stack>#include<queue>#include<map>#include<stdio.h>#include<stdlib.h>#include<ctype.h>#inclu
阅读更多...
第10章 中断和动态时钟显示

第10章 中断和动态时钟显示

第10章 中断和动态时钟显示 从本章开始，按照书籍的划分，第10章开始就进入保护模式（Protected Mode）部分了，感觉从这里开始难度突然就增加了。 书中介绍了为什么有中断（Interrupt）的设计，中断的几种方式：外部硬件中断、内部中断和软中断。通过中断做了一个会走的时钟和屏幕上输入字符的程序。 我自己理解中断的一些作用： 为了更好的利用处理器的性能。协同快速和慢速设备一起工作
阅读更多...
poj2576(二维背包)

poj2576(二维背包)

题意：n个人分成两组，两组人数只差小于1 ， 并且体重只差最小 对于人数要求恰好装满，对于体重要求尽量多，一开始没做出来，看了下解题，按照自己的感觉写，然后a了 状态转移方程：dp[i][j] = max(dp[i][j],dp[i-1][j-c[k]]+c[k]);其中i表示人数，j表示背包容量，k表示输入的体重的 代码如下： #include<iostream>#include<
阅读更多...
hdu2159（二维背包）

hdu2159（二维背包）

这是我的第一道二维背包题，没想到自己一下子就A了，但是代码写的比较乱，下面的代码是我有重新修改的 状态转移：dp[i][j] = max(dp[i][j], dp[i-1][j-c[z]]+v[z]); 其中dp[i][j]表示，打了i个怪物，消耗j的耐力值，所得到的最大经验值 代码如下： #include<iostream>#include<algorithm>#include<
阅读更多...
csu(背包的变形题)

csu(背包的变形题)

题目链接 这是一道背包的变形题目。好题呀 题意:给n个怪物，m个人，每个人的魔法消耗和魔法伤害不同，求打死所有怪物所需的魔法 #include<iostream>#include<algorithm>#include<cstring>#include<stack>#include<queue>#include<set>//#include<u>#include<map
阅读更多...
hdu1011（背包树形DP）

hdu1011（背包树形DP）

没有完全理解这题， m个人，攻打一个map，map的入口是1，在攻打某个结点之前要先攻打其他一个结点 dp[i][j]表示m个人攻打以第i个结点为根节点的子树得到的最优解 状态转移dp[i][ j ] = max(dp[i][j], dp[i][k]+dp[t][j-k]),其中t是i结点的子节点 代码如下： #include<iostream>#include<algorithm
阅读更多...
hdu1171（母函数或多重背包）

hdu1171（母函数或多重背包）

题意：把物品分成两份，使得价值最接近 可以用背包，或者是母函数来解，母函数（1 + x^v+x^2v+.....+x^num*v）（1 + x^v+x^2v+.....+x^num*v）（1 + x^v+x^2v+.....+x^num*v） 其中指数为价值，每一项的数目为（该物品数+1）个 代码如下： #include<iostream>#include<algorithm>
阅读更多...
动态规划---打家劫舍

动态规划---打家劫舍

题目： 你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。 给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。 思路： 动态规划五部曲： 1.确定dp数组及含义 dp数组是一维数组，dp[i]代表
阅读更多...
购买磨轮平衡机时应该注意什么问题和技巧

购买磨轮平衡机时应该注意什么问题和技巧

在购买磨轮平衡机时，您应该注意以下几个关键点： 平衡精度 平衡精度是衡量平衡机性能的核心指标，直接影响到不平衡量的检测与校准的准确性，从而决定磨轮的振动和噪声水平。高精度的平衡机能显著减少振动和噪声，提高磨削加工的精度。 转速范围 宽广的转速范围意味着平衡机能够处理更多种类的磨轮，适应不同的工作条件和规格要求。 振动监测能力 振动监测能力是评估平衡机性能的重要因素。通过传感器实时监
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2