动态规划法C++实现最大k乘积问题

2023-10-13 00:59

本文主要是介绍动态规划法C++实现最大k乘积问题,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

最大K乘积问题
问题描述
设I是一个n位十进制整数。如果将I划分为k段,则可得到k个整数。这k个整数的乘积称为I的一个k乘积。试设计一个算法,对于给定的I和k,求出I的最大k乘积。
例如十进制整数 1234 划分为 3 段可有如下情形:
1 × 2 × 34 = 68
1 × 23 × 4 = 92
12 × 3 × 4 = 144
编程任务
对于给定的I 和k,编程计算I 的最大k 乘积。
数据输入
输入的第1 行中有2个正整数n和k。正整数n是序列的长度;正整数k是分割的段数。接下来的一行中是一个n位十进制整数。(n<=10)
结果输出
计算出的最大k乘积。
输入文件示例 输出文件示例
input.txt output.txt
3 2
312 62

问题分析
首先用反证法证明最大k乘积问题具有最优子结构性质,从而证明该题目适合使用动态规划法:
(1)假设n位十进制整数I的最大k乘积记为f(n,k),前k-1段总共是m位,且1<=m<n,则最后一段为n-m位,用I(m,n-m)表示从第m位开始的最后n-m位十进制数,则f(n,k)=f(m,k-1)*I(m,n-m).
(2)现在我们假设前面m位十进制整数的最大k-1乘积不是f(m,k-1),而是H(m,k-1),则有H(m,k-1)>f(m,k-1), 左右两边同时乘以I(m,n-m)得H(m,k-1)*I(m,n-m)>f(m,k-1)*I(m,n-m)=f(n,k) 即f(n,k)不是I的最大K乘积与最初的假设相矛盾。
(3)所以f(m,k-1)是前面m位十进制整数的最大k-1乘积,即最大k乘积问题具有最优子结构性质。这说明可以使用动态规划来求解。
算法步骤:
(1)
1.1设tempArr(h,k) 表示: 从第h位到第k位所组成的十进制数
1.2设dp(i,j)表示前i位(1-i)分成j段所得的最大乘积,
1.3arr数组储存给定的n个数字 ;
1.4首先将连续数字第i位到第j位表示的十进制数放在tempArr数组,dp[i][j]代表前i位有j个乘号。
(2)写出动态方程:
如果只分成一段,那么dp[i][1]=tempArr[1][i];
否则: 前i位(1~i)数字分j组乘积的最大值等于分为j-1组的结果再乘以一个后面剩下的数字组成所代表的的十进制数。
dp[i][j]=max(dp[i][j],dp[k][j-1]*tempArr[k+1][i]); 1<=k<i;
(3)最终的结果dp[n][k-1]即为最大k乘积
代码实现:

#include<iostream>
#include <fstream>
#include <string>
#include <sstream>
#include<algorithm>
#include<vector>
#define MAX 20
using namespace std;//数字的位数
int  n = 0;
//分成k段
int k = 0;
//给定的数字
int value = 0;
//存储给定数组的每一个数字
int* arr = NULL;
//存储k乘积最大值
int arr2D[MAX][MAX];
//临时存放第i个到第j个数字表示的十进制数
int tempArr[MAX][MAX];
/*
读取给定的data.txt文件的数据
读取第一行的n , k
第二行的数字 并将每一个数组存储到arr数组中
*/
void readTextData()
{//data.txt为你自己的输入文件路径ifstream ifs("data.txt", ios::in | ios::binary); // 改成你要打开的文件if (ifs.is_open()) {//读取字符的缓冲容器char buf[100];//临时装载读取的元素string s = "";//控制是否读取结束bool fla = false;int count = 0;memset(buf,' ',100);while (!ifs.eof()){//读取文本内容到缓冲容器中ifs.read(buf, 100);for (int i = 0; i < 100; i++) {if (!isspace(buf[i])){//读取遇到空格前的数据,比如" 12 3  4",分别读取为:s="12",s="3",s="4"s += buf[i];}else {if (count  == 0){n = atoi(s.c_str());arr = new int[n];count++;s = "";}else if (count == 1) {k = atoi(s.c_str());count++;s = "";}else if (count == 2){if (buf[i] == '\r' || buf[i] == '\n'){continue;}else{value = atoi(s.c_str());for (int j = 0; j < s.length(); j++){arr[j] = s[j] - 48;}fla = true;break;}}}}if (fla == true){break;}}cout << "输入的数据为:";for (int  i = 0; i < n; i++){cout << arr[i];}cout << endl;ifs.close();}else {cout << "打开文件失败" << endl;}}/*
@to do:将读取到的value从第i个到第j个数字表示的十进制值存储到一个数组中
*/
void init()
{for (int i = 1; i <= n; i++){//给数组对角线赋值tempArr[i][i] = arr[i - 1];}for (int i = 1; i <= n; i++){for (int j = i + 1; j <= n; j++){//获取每个第i到第j位表示的十进制数tempArr[i][j] = tempArr[i][j - 1] * 10 + tempArr[j][j];}}}
int getValue() 
{//枚举前i个数字 for (int i = 1; i <= n; i++)  {//枚举乘号个数  for (int j = 0; j < i; j++){if (j == 0){arr2D[i][j] = tempArr[1][i]; continue;}//枚举乘号位置   for (int k = 1; k < i; k++){//找到最大的k乘积arr2D[i][j] = max(arr2D[i][j], arr2D[k][j - 1] * tempArr[k + 1][i]);}}}//返回最终结果return arr2D[n][k-1];
}int main()
{readTextData();init();int result = getValue();cout <<"最大"<<k<<"乘积结果为:"<< result << endl;system("pause");return 0;
}

当data.txt文件输入为:
在这里插入图片描述
输出结果:
在这里插入图片描述
实验分析:
根据算法我们知道使用了一个一维数组arr,两个二维数组tempArr和dp,所以该算法的空间复杂度为O(nn),在函数init()初始化过程中,使用了两个嵌套的for循环,时间复杂度为O(nn),在getValue()函数中,使用了三个for循环,时间复杂度为O(nnn),所以该算法的时间复杂度为O(nnn)

这篇关于动态规划法C++实现最大k乘积问题的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

基于Python实现一个图片拆分工具

《基于Python实现一个图片拆分工具》这篇文章主要为大家详细介绍了如何基于Python实现一个图片拆分工具,可以根据需要的行数和列数进行拆分,感兴趣的小伙伴可以跟随小编一起学习一下... 简单介绍先自己选择输入的图片,默认是输出到项目文件夹中,可以自己选择其他的文件夹,选择需要拆分的行数和列数,可以通过

一文详解SpringBoot中控制器的动态注册与卸载

《一文详解SpringBoot中控制器的动态注册与卸载》在项目开发中,通过动态注册和卸载控制器功能,可以根据业务场景和项目需要实现功能的动态增加、删除,提高系统的灵活性和可扩展性,下面我们就来看看Sp... 目录项目结构1. 创建 Spring Boot 启动类2. 创建一个测试控制器3. 创建动态控制器注

Python中将嵌套列表扁平化的多种实现方法

《Python中将嵌套列表扁平化的多种实现方法》在Python编程中,我们常常会遇到需要将嵌套列表(即列表中包含列表)转换为一个一维的扁平列表的需求,本文将给大家介绍了多种实现这一目标的方法,需要的朋... 目录python中将嵌套列表扁平化的方法技术背景实现步骤1. 使用嵌套列表推导式2. 使用itert

Python使用pip工具实现包自动更新的多种方法

《Python使用pip工具实现包自动更新的多种方法》本文深入探讨了使用Python的pip工具实现包自动更新的各种方法和技术,我们将从基础概念开始,逐步介绍手动更新方法、自动化脚本编写、结合CI/C... 目录1. 背景介绍1.1 目的和范围1.2 预期读者1.3 文档结构概述1.4 术语表1.4.1 核

在Linux中改变echo输出颜色的实现方法

《在Linux中改变echo输出颜色的实现方法》在Linux系统的命令行环境下,为了使输出信息更加清晰、突出,便于用户快速识别和区分不同类型的信息,常常需要改变echo命令的输出颜色,所以本文给大家介... 目python录在linux中改变echo输出颜色的方法技术背景实现步骤使用ANSI转义码使用tpu

Python使用python-can实现合并BLF文件

《Python使用python-can实现合并BLF文件》python-can库是Python生态中专注于CAN总线通信与数据处理的强大工具,本文将使用python-can为BLF文件合并提供高效灵活... 目录一、python-can 库:CAN 数据处理的利器二、BLF 文件合并核心代码解析1. 基础合

Python使用OpenCV实现获取视频时长的小工具

《Python使用OpenCV实现获取视频时长的小工具》在处理视频数据时,获取视频的时长是一项常见且基础的需求,本文将详细介绍如何使用Python和OpenCV获取视频时长,并对每一行代码进行深入解析... 目录一、代码实现二、代码解析1. 导入 OpenCV 库2. 定义获取视频时长的函数3. 打开视频文

golang版本升级如何实现

《golang版本升级如何实现》:本文主要介绍golang版本升级如何实现问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录golanwww.chinasem.cng版本升级linux上golang版本升级删除golang旧版本安装golang最新版本总结gola

SpringBoot中SM2公钥加密、私钥解密的实现示例详解

《SpringBoot中SM2公钥加密、私钥解密的实现示例详解》本文介绍了如何在SpringBoot项目中实现SM2公钥加密和私钥解密的功能,通过使用Hutool库和BouncyCastle依赖,简化... 目录一、前言1、加密信息(示例)2、加密结果(示例)二、实现代码1、yml文件配置2、创建SM2工具

Mysql实现范围分区表(新增、删除、重组、查看)

《Mysql实现范围分区表(新增、删除、重组、查看)》MySQL分区表的四种类型(范围、哈希、列表、键值),主要介绍了范围分区的创建、查询、添加、删除及重组织操作,具有一定的参考价值,感兴趣的可以了解... 目录一、mysql分区表分类二、范围分区(Range Partitioning1、新建分区表:2、分