钢条切割问题的解法(C/C++)

2024-06-09 09:58
文章标签 c++ 问题 解法 切割 钢条

本文主要是介绍钢条切割问题的解法(C/C++),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

(原题见算法导论·动态规划)

对长度为n的钢条进行切割,对应的切割长度和价格对应如下:

int cost[] = {0, 1, 5, 8, 9, 10, 17, 17, 20, 24, 30};

比如1对应价值1,10对应价值30。即相应的下标和值的对应。现求切割所得最大效益mx。


1.递归算法:

//g++ 编译通过int cut_rod(int *cost,int n)
{if(n == 0) return 0;int limit = MIN(n,10);       //分割第一条的上限int mx =  -1;for(int i = 1;i <= limit; ++i)mx = maxnum(mx,cost[i]+cut_rod(cost,n-i));    //取当前值于递归值的最大值return mx;
}


由于对相同子问题的重复求解,T(n) = 2^n


2.递归标记数组算法:(自顶而下)(DFS)

//g++ 编译通过int mem_cut_rod(int *cost,int n,int *mem)   //mem数组长度为n,所有元素须在其他函数中初始化为-1
{int mx;if (mem[n] >= 0) return mem[n];     //对于求过的问题,直接返回存储的值if (n == 0) mx = 0;else mx = -1;int limit = MIN(n,10);for(int i = 1;i <= limit; ++i)mx = maxnum(mx,cost[i]+mem_cut_rod(cost,n-i,mem));   //后面的内容和递归型是一样的mem[n] = mx;    //储存计算出的新值return mx;  
}


3.逆拓扑序DP:(自底向上)

//g++ 编译通过int bottom_cut_rod(int *cost,int n)
{int mem[MEM_LEN+1];                              //MEM_LEN = n,设置标记数组mem[0] = 0;                                       //i,j将从1开始,这里收益是0for(int i = 1; i <= n; ++i)                              //从第一个问题开始求解{int mx = -1;int limit = MIN(i,10);for(int j = 1;j <= limit; ++j)mx = maxnum(mx,cost[j] + mem[i-j]);     //求解最小的问题mem[i] = mx;}return mem[n];
}


我们可以看到,2,3 的解法复杂度均为O(n^2)。


4.带解决方案的DFS:

typedef struct {string path;        //方案路径bool memoried;int value;
} MEMORY;MEMORY *mem_pool;
string num_to_str(int num) {char buf[120];sprintf(buf, "%d", num);return string(buf);
}MEMORY DFS(int remain) {int select, limit = MIN(remain, COST_LEN), mx = -1, cur_cost;string cur_path, mx_path;if (mem_pool[remain - 1].memoried) {return mem_pool[remain - 1];}for (select = 1; select <= limit; ++select) {if (select == remain) {cur_cost = cost[remain];cur_path = num_to_str(remain);} else {MEMORY upper = DFS(remain - select);cur_cost = cost[select] + upper.value;cur_path = num_to_str(select) + ", " + upper.path;}if (cur_cost > mx) {mx = cur_cost;mx_path = cur_path;}}mem_pool[remain - 1].memoried = true;mem_pool[remain - 1].value = mx;mem_pool[remain - 1].path = mx_path;return mem_pool[remain - 1];
}int main() {int n, i;cin >> n;mem_pool = new MEMORY[n];if (!mem_pool) {return 1;}for (i = 0; i < n; ++i) {mem_pool[i].memoried = false;}MEMORY result = DFS(n);cout << result.value << endl;cout << result.path << endl;delete[] mem_pool;return 0;
}



最后我们附上一份c实现的优美代码:


//2015.6.2//copyright XJSoft#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>typedef struct {bool memoried;int value;
} MEMORY;int cost[] = {0, 1, 5, 8, 9, 10, 17, 17, 20, 24, 30};
MEMORY *mem_pool;#define COST_LEN 10
#define MIN(a,b) ((a)<(b)?(a):(b))
int maxnum(const int v1,const int v2)
{if (v1 > v2) return v1;else return v2;
}int DFS(int remain) {int select, limit = MIN(remain, COST_LEN), mx = -1, cur_cost;if (mem_pool[remain - 1].memoried) {return mem_pool[remain - 1].value;}for (select = 1; select <= limit; ++select) {if (select == remain) {cur_cost = cost[remain];} else {cur_cost = cost[select] + DFS(remain - select);}if (cur_cost > mx) {mx = cur_cost;}}mem_pool[remain - 1].memoried = true;mem_pool[remain - 1].value = mx;return mx;
}int DP(int n) {int remain, select, limit, mx, cur_cost;for (remain = 1; remain <= n; ++remain) {mx = -1;limit = MIN(remain, COST_LEN);for (select = 1; select <= limit; ++select) {if (select == remain) {cur_cost = cost[select];} else {cur_cost = cost[select] + mem_pool[remain - select - 1].value;}if (cur_cost > mx) {mx = cur_cost;}}mem_pool[remain - 1].value = mx;}return mem_pool[n - 1].value;
}int main() {int n, i;scanf("%d", &n);mem_pool = (MEMORY*)malloc(n * sizeof(MEMORY));if (!mem_pool) {printf("Mem error!\n");return 1;}for (i = 0; i < n; ++i) {mem_pool[i].memoried = false;}printf("%d\n", DP(n));free(mem_pool);return 0;
}


这篇关于钢条切割问题的解法(C/C++)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1044856

相关文章

详谈redis跟数据库的数据同步问题

《详谈redis跟数据库的数据同步问题》文章讨论了在Redis和数据库数据一致性问题上的解决方案,主要比较了先更新Redis缓存再更新数据库和先更新数据库再更新Redis缓存两种方案,文章指出,删除R... 目录一、Redis 数据库数据一致性的解决方案1.1、更新Redis缓存、删除Redis缓存的区别二

oracle数据库索引失效的问题及解决

《oracle数据库索引失效的问题及解决》本文总结了在Oracle数据库中索引失效的一些常见场景,包括使用isnull、isnotnull、!=、、、函数处理、like前置%查询以及范围索引和等值索引... 目录oracle数据库索引失效问题场景环境索引失效情况及验证结论一结论二结论三结论四结论五总结ora

深入理解C++ 空类大小

《深入理解C++空类大小》本文主要介绍了C++空类大小,规定空类大小为1字节,主要是为了保证对象的唯一性和可区分性,满足数组元素地址连续的要求,下面就来了解一下... 目录1. 保证对象的唯一性和可区分性2. 满足数组元素地址连续的要求3. 与C++的对象模型和内存管理机制相适配查看类对象内存在C++中,规

element-ui下拉输入框+resetFields无法回显的问题解决

《element-ui下拉输入框+resetFields无法回显的问题解决》本文主要介绍了在使用ElementUI的下拉输入框时,点击重置按钮后输入框无法回显数据的问题,具有一定的参考价值,感兴趣的... 目录描述原因问题重现解决方案方法一方法二总结描述第一次进入页面,不做任何操作,点击重置按钮,再进行下

解决mybatis-plus-boot-starter与mybatis-spring-boot-starter的错误问题

《解决mybatis-plus-boot-starter与mybatis-spring-boot-starter的错误问题》本文主要讲述了在使用MyBatis和MyBatis-Plus时遇到的绑定异常... 目录myBATis-plus-boot-starpythonter与mybatis-spring-b

mysql主从及遇到的问题解决

《mysql主从及遇到的问题解决》本文详细介绍了如何使用Docker配置MySQL主从复制,首先创建了两个文件夹并分别配置了`my.cnf`文件,通过执行脚本启动容器并配置好主从关系,文中还提到了一些... 目录mysql主从及遇到问题解决遇到的问题说明总结mysql主从及遇到问题解决1.基于mysql

如何测试计算机的内存是否存在问题? 判断电脑内存故障的多种方法

《如何测试计算机的内存是否存在问题?判断电脑内存故障的多种方法》内存是电脑中非常重要的组件之一,如果内存出现故障,可能会导致电脑出现各种问题,如蓝屏、死机、程序崩溃等,如何判断内存是否出现故障呢?下... 如果你的电脑是崩溃、冻结还是不稳定,那么它的内存可能有问题。要进行检查,你可以使用Windows 11

如何安装HWE内核? Ubuntu安装hwe内核解决硬件太新的问题

《如何安装HWE内核?Ubuntu安装hwe内核解决硬件太新的问题》今天的主角就是hwe内核(hardwareenablementkernel),一般安装的Ubuntu都是初始内核,不能很好地支... 对于追求系统稳定性,又想充分利用最新硬件特性的 Ubuntu 用户来说,HWEXBQgUbdlna(Har

在 VSCode 中配置 C++ 开发环境的详细教程

《在VSCode中配置C++开发环境的详细教程》本文详细介绍了如何在VisualStudioCode(VSCode)中配置C++开发环境,包括安装必要的工具、配置编译器、设置调试环境等步骤,通... 目录如何在 VSCode 中配置 C++ 开发环境:详细教程1. 什么是 VSCode?2. 安装 VSCo

MAVEN3.9.x中301问题及解决方法

《MAVEN3.9.x中301问题及解决方法》本文主要介绍了使用MAVEN3.9.x中301问题及解决方法,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面... 目录01、背景02、现象03、分析原因04、解决方案及验证05、结语本文主要是针对“构建加速”需求交