【算法设计与分析】实验报告c++实现(矩阵链相乘问题、投资问题、背包问题、TSP问题、数字三角形)

一、实验目的

1．加深学生对动态规划算法设计方法的基本思想、基本步骤、基本方法的理解与掌握；
2．提高学生利用课堂所学知识解决实际问题的能力；
3．提高学生综合应用所学知识解决实际问题的能力。

二、实验任务

1、矩阵链相乘问题

image-20240404002318769
2、投资问题

image-20240404002332398

3、背包问题

img

4、TSP问题
旅行家要旅行n个城市，要求经历各个城市且仅经历一次，然后回到出发城市，并要求所走的路程最短。
5、数字三角形
问题描述：在上面的数字三角形中寻找一条从顶部到底边的路径，使得路径上所经过的数字之和最大。路径上的每一步都只能往左下或右下走。

image-20240404002353934

三、实验设备及编程开发工具

笔记本，Windows10操作系统，Dev-C++，Pycharm

四、实验过程设计（算法设计过程）

（一）、矩阵链相乘问题

(1) 算法分析：
输入P=< P0, P1, …, Pn>，Ai…j 表示乘积 AiAi+1…Aj 的结果，其最后一次相乘是：

img

m[i,j] 表示得到Ai…j的最少的相乘次数。
递推方程：

img

为了确定加括号的次序，设计表s[i,j],记录求得最优时最一位置。
(2) 算法实现：

import sys
import time

gk = lambda i, j: str(i)+','+str(j)
MAX = sys.maxsize  # 获取最大的整数


def memorized_matrix_chain(p):
    n = len(p)-1
    m = {}
    for i in range(1, n+1):
        for j in range(i, n+1):
            m[gk(i, j)] = MAX  # 先初始化为最大值

    return lookup_chain(m, p, 1, n)

def lookup_chain(m, p, i, j):
    if m[gk(i, j)] < MAX:
        return m[gk(i, j)]
    if i == j:
        m[gk(i, j)] = 0
    else:
        for k in range(i, j):
            # 依次求出每段的最小的值   p = [P0,P1，……，Pn] 矩阵链 第一个矩阵为P0*P1
            q = lookup_chain(m, p, i, k) + lookup_chain(m, p, k+1, j) + p[i-1]*p[k]*p[j]
            # 找出最优的解
            if q < m[gk(i, j)]:
                m[gk(i, j)] = q

    # 输出每一步的结果
    # print("______")
    # print(m)
    return m[gk(i, j)]

def main():
    p = [30, 35, 15, 5, 10, 20, 25, 5, 16, 34, 28, 19, 66, 34, 78, 55, 23]
    # p = [30, 15, 10, 20, 5]
    print(memorized_matrix_chain(p))

if __name__ == '__main__':
    b = time.time()
    main()
    print('total run time is:', time.time()-b)

（二）、投资问题

(1) 问题分析：
子问题界定:由参数k和x界定
k: 考虑对项目1,2,…,k的投资
x: 投资总数不超过x
矩阵链相乘里边的i,j代表的是矩阵的下标,是同样的参数,这里两个参数k,x是不同的参数。
原始问题输入:
k=n，x=m
子问题的计算顺序:k=1,2,3,…,n
对于给定的k,计算x=1,2,3,…,m
优化函数的递推方程:
Fk(x): x元钱投资给前k个项目的最大收益

多步判断:
如果知道p元钱(0≤p≤x)投给前k−1个项目的最大效益Fk−1§,就可以进行x元钱投给前k个项目的最优决策

递推方程和边界条件：
Fk(x)=max0≤xk≤x{fk(xk)+Fk−1(x−xk)},1<k≤n
F1(x)=f1(x)
第一个项目投资决策: 投资第一个项目的钱不超过x，x∈[0,m]的最大收益就是f1(x),x∈[0,m]不需要计算.
第二项目投资决策: 第二个投资F2(x)，是当xk，xk∈[0,x]元钱投资给第二个项目得到的效益加上x−xk元钱投资给前一个项目的最优.然后再在这里面取最大值,就是最优决策.直到决策
第n个项目的投资: 第n个投资Fn(x)是当xk，xk∈[0,x]元钱投资给第n个项目得到的效益加上x−xk元钱投资给前n−1个项目的最优.然后再在这里面取最大值,就是最优决策.

(2) 算法实现：

#define MAX_N 105 // 最大投资项目数目
#define MAX_M 105 // 最大投资钱数

int n,m; // n个项目,投资m万元
int f[MAX_N][MAX_M]; // 第i项投资j万元的收益 1 <= i <= n, 1 <= j <= m
int F[MAX_N][MAX_M]; // 投资前i项项目不超过j元钱的最大收益 1 <= i <= n, 1 <= j <= m
int x[MAX_N][MAX_M]; // 标记函数

// 打印计算结果
void printAns(){
    int i,j;
    for(i = 0; i <= n; i++){
        for(j = 0; j <= m; j++){
            printf("(%d,%d)\t", F[i][j], x[i][j]);
        }
        printf("\n");
    }
    printf("%d\n", F[n][m]);
}

// 动态规划算法实现, 时间复杂度O(nm^2)
void solve(){
    int i,j,k,tmp;
    for(i = 2; i <= n; i++) memset(F[i], -1, sizeof(int)*(m+1)); // 设置最大收益值的最小数目是-1
    for(i = 0; i <= m; i++) F[1][i] = f[1][i]; // 投资第一个项目
    for(i = 2; i <= n; i++){ // 投资前i个项目
        F[i][0] = 0; // 投资前i个项目不超过0元的收益是0
        x[i][0] = 0; // 标记
        for(j = 1; j <= m; j++){ // 投资钱数不超过j
            for(k = 0; k <= j; k++){ // 投资当前项目的钱数
                tmp = f[i][k]+F[i-1][j-k];
                if(tmp > F[i][j]){
                    F[i][j] = tmp; // 更新当前的最有解
                    x[i][j] = k; // 更新标记函数
                }
            }
        }
    }
    printAns(); // 打印结果
}

int main(){
    //freopen("in.txt", "r", stdin);
    int i,j;
    while(~scanf("%d%d", &n, &m) && n && m){ // 输入项目数,投资钱数
        for(i = 1; i <= n; i++){ // 输入效益函数
            f[i][0] = 0; // 投资0元的投资收益是0
            for(j = 1; j <= m; j++) scanf("%d", &f[i][j]);
        }
        solve();
    }
    return 0;
}

（三）、背包问题

(1) 问题分析：
a) 把背包问题抽象化（X1，X2，…，Xn，其中Xi取0或1，表示第i个物品选或不选），Vi表示第i个物品的价值，Wi表示第i个物品的体积（重量）；

b)建立模型，即求max(V1X1+V2X2+…+VnXn)；

c)约束条件，W1X1+W2X2+…+WnXn<capacity；

d)定义V(i，j)：当前背包容量j，前i个物品最佳组合对应的价值；

e)最优性原理是动态规划的基础，最优性原理是指“多阶段决策过程的最优决策序列具有这样的性质：不论初始状态和初始决策如何，对于前面决策所造成的某一状态而言，其后各阶段的决策序列必须构成最优策略”。

(2) 算法实现：

import numpy as np
# 行李数n，不超过的重量W，重量列表w和价值列表p
def fun(n, W, w, p):
    a = np.array([[0] * (W + 1)] * (n + 1))
    # 依次计算前i个行李的最大价值，n+1在n的基础上进行
    for i in range(1, n + 1):
        for j in range(1, W + 1):
            if w[i - 1] > j:
                a[i, j] = a[i - 1, j]
            else:
                a[i, j] = max(a[i - 1, j], p[i - 1] + a[i - 1, j - w[i - 1]])  # 2种情况取最大值
    # print(a)
    print('max value is：' + str(a[n, W]))
    findDetail(p, n, a[n, W])


# 找到价值列表中的一个子集，使得其和等于前面求出的最大价值，即为选择方案
def findDetail(p, n, v):
    a = np.array([[True] * (v + 1)] * (n + 1))
    for i in range(0, n + 1):
        a[i][0] = True
    for i in range(1, v + 1):
        a[0][i] = False
    for i in range(1, n + 1):
        for j in range(1, v + 1):
            if p[i - 1] > j:
                a[i, j] = a[i - 1, j]
            else:
                a[i, j] = a[i - 1, j] or a[i - 1, j - p[i - 1]]
    if a[n, v]:
        i = n
        result = []
        while i >= 0:
            if a[i, v] and not a[i - 1, v]:
                result.append(p[i - 1])
                v -= p[i - 1]
            if v == 0:
                break
            i -= 1
        print(result)
    else:
        print('error')


# 初始化权重和价格
weights = [1, 2, 5, 6, 7, 9]
price = [1, 6, 18, 22, 28, 36]
#  设置背包的最大重量为13
fun(len(weights), 13, weights, price)

(四)TSP问题

(1) 问题分析：
假定从城市1出发，经过了一些地方，并到达了城市j。毋庸置疑，我们需要记录的信息有当前的城市j。同时我们还需要记录已经走过的城市的集合。同理，使用S记录未走过的城市的集合也可以的，且运算方便。
于是可以得出状态转移方程 go(S,init)=min{go(S−i,i)+dp[i][init]}∀s∈S
go(s,init)表示从init点开始，要经过s集合中的所有点的距离
因为是NP问题，所以时间复杂度通常比较大。使用dis[s][init]用来去重，初始化为-1，如果已经计算过init—>S（递归形式），则直接返回即可。

(2) 算法实现：

import pandas as pd
import numpy as np
import math
import time

# 读取城市的数据
dataframe = pd.read_csv("./data/TSP10cities.tsp", sep=" ", header=None)
v = dataframe.iloc[:, 1:3]

train_v= np.array(v)
train_d=train_v
dist = np.zeros((train_v.shape[0],train_d.shape[0]))

#计算距离矩阵
for i in range(train_v.shape[0]):
    for j in range(train_d.shape[0]):
        dist[i, j] = math.sqrt(np.sum((train_v[i,:]-train_d[j,:])**2))

"""
N:城市数
s:二进制表示，遍历过得城市对应位为1，未遍历为0
dp:动态规划的距离数组
dist：城市间距离矩阵
sumpath:目前的最小路径总长度
Dtemp：当前最小距离
path:记录下一个应该到达的城市
"""

N=train_v.shape[0]
path = np.ones((2**(N+1),N))
dp = np.ones((2**(train_v.shape[0]+1),train_d.shape[0]))*-1


def TSP(s, init, num):
    if dp[s][init] != -1:
        return dp[s][init]
    if s == (1 << (N)):
        return dist[0][init]
    sumpath=1000000000
    for i in range(N):
        if s &(1<<i):
            m = TSP(s&(~(1<<i)),i,num+1)+dist[i][init]
            if m < sumpath:
                sumpath = m
                path[s][init]=i
    dp[s][init] = sumpath
    return dp[s][init]


if __name__ == "__main__":
    init_point=0
    s=0
    for i in range(1,N+1):
        s=s|(1<<i)
    start = time.clock()
    distance=TSP(s,init_point,0)
    end = time.clock()
    s=0b11111111110
    init=0
    num=0
    print(distance)
    while True:
        print(path[s][init])
        init=int(path[s][init])
        s=s&(~(1<<init))
        num+=1
        if num>9:
            break
    print("程序的运行时间是：%s"%(end-start))

五、实验结果及算法复杂度分析

（一） 矩阵链相乘问题
1 实验结果

img

（二）投资最少问题
1 实验结果

img

时间复杂度 O ( n m 2 ) O(nm^2) O(nm2)

（三）背包问题
1 实验结果

img

（四）TSP问题
img

实验小结（包括问题和解决方法、心得体会等）

通过本次实验，利用C/C++、python语言编程实现解决了矩阵链相乘问题，投资问题，背包问题以及TSP问题。对于投资问题，python的实现没有实现出来，存在问题，使用了C语言成功实现。通过本次实验，也进一步加深的对动态规划算法的认识。

本次实验增加了动手编码能力，对动态规划算法有了更神的认识，同时也对算法设计有了更进一步的认识，但是技术上的缺陷，编码能力上存在的短板，在今后的实验中还需要加大练习力度。

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/589762.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

Mac环境下ollama部署和体验

Mac环境下ollama部署和体验

欢迎访问我的GitHub 这里分类和汇总了欣宸的全部原创(含配套源码)&#xff1a;https://github.com/zq2599/blog_demos 关于ollama ollama和LLM&#xff08;大型语言模型&#xff09;的关系&#xff0c;类似于docker和镜像&#xff0c;可以在ollama服务中管理和运行各种LLM&…
阅读更多...
Java | Leetcode Java题解之第63题不同路径II

Java | Leetcode Java题解之第63题不同路径II

题目&#xff1a; 题解&#xff1a; class Solution {public int uniquePathsWithObstacles(int[][] obstacleGrid) {int n obstacleGrid.length, m obstacleGrid[0].length;int[] f new int[m];f[0] obstacleGrid[0][0] 0 ? 1 : 0;for (int i 0; i < n; i) {for (i…
阅读更多...
spring boot学习第十八篇:使用clickhouse

spring boot学习第十八篇:使用clickhouse

1、pom.xml文件内容如下&#xff1a; <?xml version"1.0" encoding"UTF-8"?> <project xmlns"http://maven.apache.org/POM/4.0.0"xmlns:xsi"http://www.w3.org/2001/XMLSchema-instance"xsi:schemaLocation"http://…
阅读更多...
Vitis HLS 学习笔记--MAXI手动控制突发传输

Vitis HLS 学习笔记--MAXI手动控制突发传输

目录 1. 简介 2. MAXI 突发传输详解 2.1 突发传输的前置条件 2.2 hls::burst_maxi 详解 2.2.1 基本知识 2.2.2 hls::burst_maxi 构造函数 2.2.3 hls::burst_maxi 读取方法 2.2.4 hls::burst_maxi 写入方法 2.3 示例一 2.4 示例二 3. 总结 1. 简介 这篇文章探讨了在…
阅读更多...
win11 Terminal 部分窗口美化

win11 Terminal 部分窗口美化

需求及分析&#xff1a;因为在 cmd、anaconda prompt 窗口中输入命令较多&#xff0c;而命令输入行和输出结果都是同一个颜色&#xff0c;不易阅读&#xff0c;故将需求定性为「美化窗口」。 美化结束后&#xff0c;我在想是否能不安装任何软件&#xff0c;简单地通过调整主题颜…
阅读更多...
前端高频算法

前端高频算法

分析算法排序&#xff1a; 时间复杂度: 一个算法执行所耗费的时间。 空间复杂度: 运行完一个程序所需内存的大小。 执行效率、内存消耗、稳定性 三方面入手。 1. 排序 1.1 冒泡排序 冒泡的过程只涉及相邻数据的交换操作&#xff0c;所以它的空间复杂度为 O(1)。 为了保证…
阅读更多...
详细设计（上）

详细设计（上）

结构程序化 三种基本控制结构 其他常用控制结构 人机界面设计 三条“黄金规则” 1、置用户于控制之下 2、减少用户记忆负担 3、保持界面一致 设计问题 设计人机界面过程中会遇到的4个问题&#xff1a; 1、系统响应时间 2、用户帮助设施 3、出错信息处理 4、命令交互 设计过…
阅读更多...
每日算法之二叉树的层序遍历

每日算法之二叉树的层序遍历

题目描述 给你二叉树的根节点 root &#xff0c;返回其节点值的 层序遍历 。 &#xff08;即逐层地&#xff0c;从左到右访问所有节点&#xff09;。 示例 1&#xff1a; 输入&#xff1a;root [3,9,20,null,null,15,7] 输出&#xff1a;[[3],[9,20],[15,7]] 示例 2&#…
阅读更多...
tensorflow报错

tensorflow报错

参考 TensorFlow binary is optimized to use available CPU instructions in performance-critical operations._this tensorflow binary is optimized to use availab-CSDN博客 解决Python中cuBLAS插件无法注册问题_unable to register cudnn factory: attempting to re-CS…
阅读更多...
采用“3+1”模式，开展新部门组建的各项工作解决思路

采用“3+1”模式，开展新部门组建的各项工作解决思路

【背景】 A公司成立于2000年&#xff0c;位于浙江省杭州市&#xff0c;是一家大中型即将上市的公司&#xff0c;近年来发展一直不错&#xff1b;同时A公司还有另外一个产业是国家级公共服务平台&#xff0c;由“1平台”、“6中心”构成&#xff0c;主要围绕园区及区域做服务。…
阅读更多...
搭建智能客服机器人设计流程

搭建智能客服机器人设计流程

一、检索型机器人FAQ-Bot 在客服处理的问题中70%都是简单的问答业务&#xff0c;只要找到QA知识库中与用户当前问句语义最相近的标准问句&#xff0c;取出答案给用户就可以了。FAQ-Bot就是处理这类问题的。在没有使用深度学习算法之前&#xff0c;通常采用检索NLP技术处理。 …
阅读更多...
深入图像分类：使用美国手语数据集训练定制化神经网络

深入图像分类：使用美国手语数据集训练定制化神经网络

引言 在前一篇博客中&#xff0c;我们探讨了如何使用MNIST数据集训练一个基础的神经网络来进行手写数字识别。在本文中&#xff0c;我们将更进一步&#xff0c;使用美国手语字母表&#xff08;ASL&#xff09;数据集来构建一个定制化的图像分类模型。通过这个过程&#xff0c;…
阅读更多...
免费通配符证书的申请指南——从申请到启动https

免费通配符证书的申请指南——从申请到启动https

如果您的网站拥有众多二级子域名&#xff0c;那么通配符证书证书是最好的选择。 免费通配符申请流程如下&#xff1a; 1 创建证书服务商账号 首先选择一个提供免费通配符的服务商&#xff0c;打开国产服务商JoySSL官网&#xff0c;创建一个账号&#xff08;注册账号时填写注册…
阅读更多...
分享自己一篇在亚马逊云科技AWS官网发的Blog技术文章

分享自己一篇在亚马逊云科技AWS官网发的Blog技术文章

小李哥在亚马逊AWS官网&#xff0c;作为第一作者发了自己的第一篇AWS Blog文章&#xff0c;也是自己今年在AWS官网的第11篇文章。文章主要内容是描述为出海的金融企业&#xff0c;搭建满足PCI-DSS合规、FIPS 140-2 Level 3安全标准的传输中数据加密云端方案&#xff0c;主要用于…
阅读更多...
CSS优惠券、卡券样式绘制

CSS优惠券、卡券样式绘制

实现左右凹陷中间有虚线效果 效果图 实现思路 从效果图可以看到这个优惠券是左右两边凹陷&#xff0c;中间还有一条虚线&#xff0c;为了封装后插槽使用方便&#xff0c;把优惠券以虚线为准分了两部分。这样布局的好处是上部分内容和下部分都可以自定义&#xff0c;不受内容限…
阅读更多...
如何搭建本地的 NPM 私有仓库 Nexus

如何搭建本地的 NPM 私有仓库 Nexus

NPM 本地私有仓库&#xff0c;是在本地搭建NPM私有仓库&#xff0c;对公司级别的组件库进行管理。在日常开发中&#xff0c;经常会遇到抽象公共组件的场景&#xff0c;在项目内部进行公用。新的项目开始时&#xff0c;也会拷贝一份创建一个新的项目&#xff0c;这样做不易于管理…
阅读更多...
芯片的可靠性测试项目有哪些？

芯片的可靠性测试项目有哪些？

知识星球&#xff08;星球名&#xff1a;芯片制造与封测社区&#xff0c;星球号&#xff1a;63559049&#xff09;里的学员问&#xff1a;封装的可靠性测试都测哪些项目呢&#xff1f; 什么是可靠性测试&#xff1f; 芯片的可靠性测试是针对芯片进行的一系列严格的测试&#x…
阅读更多...
量子城域网建设设备系列（二）：量子密钥管系统（KMS）

量子城域网建设设备系列（二）：量子密钥管系统（KMS）

在上文介绍光量子交换机的文章中我们提到&#xff0c;量子保密通信网络的通道切换是由量子密钥管理系统&#xff08;Key Management System&#xff0c;KMS&#xff09;给光量子交换机下发信道切换指令&#xff0c;实现整个网络中任意两对量子密钥分发终端的量子信道互联互通&a…
阅读更多...
2024.5.3

2024.5.3

C风格字符串的越界异常处理 #include <iostream> #include <cstring> using namespace std; class MyStr{char str[200]; public:void set(string str);char at(unsigned int a); }; void MyStr::set(string str){strcpy(this->str,str.c_str()); } char MyStr…
阅读更多...
UI-Diffuser——使用生成式扩散模型的UI原型设计算法解析

UI-Diffuser——使用生成式扩散模型的UI原型设计算法解析

概述。 移动UI是影响参与度的一个重要因素&#xff0c;例如用户对应用的熟悉程度和使用的便利性。如果你有一个类似的应用程序&#xff0c;你可能会选择一个具有现代、好看的设计的应用程序&#xff0c;而不是一个旧的设计。然而&#xff0c;要从头开始研究什么样的UI最适合应…
阅读更多...
最新文章

Copyright @ 2022~2023