精华内容
下载资源
问答
  • 动态规划算法-多边形游戏。回溯法-符号三角形问题。贪心算法-计算加油次数。包括流程图+代码+实验结果截屏+实验总结。
  • 同时复习动态规划算法、贪心算法。 实验要求:分别用伪代码或流程图或步骤分析图描述利用动态规划、贪心策略、回溯法的算法解决方案,再用程序实现,计算时间复杂度,记录最终测试数据和测试结果,运行时间。 旅行商...

    实验四:算法综合练习

    第一次写博客,写的不好,大家如果觉得有用就三连一下/手动狗头
    实验目的:掌握回溯算法的设计思想、具体实现和时间复杂度分析。同时复习动态规划算法、贪心算法。
    实验要求:分别用伪代码或流程图或步骤分析图描述利用动态规划、贪心策略、回溯法的算法解决方案,再用程序实现,计算时间复杂度,记录最终测试数据和测试结果,运行时间。

    旅行商问题
    问题描述:给定一个的整数矩阵,你要写一个程序来计算出最小权值。一条路径从列1(第一列)的任意位置开始,包括一系列的移动,最终抵达列(最后一列)。每一步均由列到列的相邻行(水平或对角)。矩阵的第一行和最后一行(行1和行)认为是相邻的,也就是说矩阵是环绕的,就像一个水平的圆柱体。合法的移动图示如下。
    在这里插入图片描述

    路径的权重就是矩阵中遍历到的所有个单元的整数值之和。例如,两个不同的矩阵如下图所示(仅最后一行的数字略有不同)。两个矩阵的最短路径如图所示。注意,右边矩阵最短路径利用了最上一行和最下一行相邻的特性。
    在这里插入图片描述

    要求:分别用动态规划算法、贪心策略、回溯法编程实现并分析。
    输入格式:
    第1行包含两个整数表示矩阵的维数:行和列,以及下面的个整数。输入的整数按行排列,即输入的第一行个整数为矩阵的第一行,第二行个整数为矩阵的第二行,以此类推。一行中的整数由一个或多个空格隔开。
    注意:行数范围,列数范围,不会存在超过30位整数表示范围的路径权值。
    输出格式:两行,第一行表示一条最小权重路径,第二行表示输出路径的权重值。路径由n个整数组成(由一个或多个空格隔开)表示最小路径的行号。如果有多于一条路径的权重为最小,则按字典顺序输出最小的一组。
    样例输入1:在这里插入图片描述

    样例输出1:
    在这里插入图片描述

    样例输入2:
    在这里插入图片描述

    样例输出2:
    在这里插入图片描述

    其他要求:构造大样本数据,测试运行结果和运行时间(可选,非必须)。可在OJ平台上测试。分析你设计的三种算法的时间复杂度。

    先上代码

    #include<stdio.h>
    #include<stdlib.h>
    
    int main()
    {
        int n, m;//m为行数,n为列数
        scanf("%d %d\n", &m, &n);
        int sum[100][100]{0};//记录每个格子的最短路劲长度
        int number[100][100]{0};//记录输入格子的长度
        int sign[100][100]{0};//记录每个格子最短路径的走向
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                scanf("%d", &number[i][j]);
                if (j == n - 1) {
                    sum[i][j] = number[i][j];
                }
            }
        }
        int min;
        for (int i = n-2; i >=0; i--) {
            min = 0;
            for (int j = 0; j < m; j++) {
                if (j == 0) {
                    if (number[j][i] + sum[m - 1][i+1] <= number[j][i] + sum[j][i+1]) {
                        min = number[j][i] + sum[m - 1][i + 1];
                        sign[j][i] = 1;
                        sum[j][i] = min;
                    }
                    else {
                        min = number[j][i] + sum[j][i + 1];
                        sign[j][i] = 0;
                        sum[j][i] = min;
                    }
                    if (min >number[j][i] + sum[j + 1][i+ 1]) {
                        min = number[j][i] + sum[j + 1][i + 1];
                        sign[j][i] = -1;
                        sum[j][i] = min;
                    }
                }
                else if (j == m - 1) {
                    if (number[j][i] + sum[j-1][i + 1] <= number[j][i] + sum[j][i + 1]) {
                        min = number[j][i] + sum[j-1][i + 1];
                        sign[j][i] = 1;
                        sum[j][i] = min;
                    }
                    else {
                        min = number[j][i] + sum[j][i + 1];
                        sign[j][i] = 0;
                        sum[j][i] = min;
                    }
                    if (min > number[j][i] + sum[0][i + 1]) {
                        min = number[j][i] + sum[0][i + 1];
                        sign[j][i] = -1;
                        sum[j][i] = min;
                    }
                }
                else {
                    if (number[j][i] + sum[j -1][i + 1] <= number[j][i] + sum[j][i + 1]) {
                        min = number[j][i] + sum[j - 1][i + 1];
                        sign[j][i] = 1;
                        sum[j][i] = min;
                    }
                    else {
                        min = number[j][i] + sum[j][i + 1];
                        sign[j][i] = 0;
                        sum[j][i] = min;
                    }
                    if (min > number[j][i] + sum[j+1][i + 1]) {
                        min = number[j][i] + sum[j+1][i + 1];
                        sign[j][i] = -1;
                        sum[j][i] = min;
                    }
                }
               
            }
        }
        /*这边是检查用的*/
        //for (int i = 0; i < m; i++) {
        //    for (int j = 0; j < n; j++) {
        //        printf("%d ", sum[i][j]);
        //    }
        //    printf("\n");
        //}
        //for (int i = 0; i < m; i++) {
        //    for (int j = 0; j < n; j++) {
        //        printf("%d ", sign[i][j]);
        //    }
        //    printf("\n");
        //}
         min=sum[0][0];
        int x = 0;//记下最小路径的行号
        for (int i = 0; i < m; i++) {
            if (min > sum[i][0]) {
                min = sum[i][0];
                x = i;
            }
        }
        min = x;
        for (int i = 0; i < n; i++) {
            printf("%d ", x + 1);
            if (sign[x][i] == 1) {
                if (x == 0) {
                    x = m - 1;
                }
                else {
                    x--;
                }
            }
            else if (sign[x][i] == -1) {
                if (x == m - 1) {
                    x = 0;
                }
                else {
                    x++;
                }
            }
        }
        printf("\n%d", sum[min][0]);
    }
    

    主要代码分析

    首先主要用到的思想是从n-1的数字开始看,分别计算n-2列的数字加上他对应的上中下的n-1的数字,最后再对比一下,小的就储存到sum二维数组里面,并且将他下一步究竟是这么走的储存到sign二维数组里面。以此类推直到到第0列。

        for (int i = n-2; i >=0; i--) {
            min = 0;
            for (int j = 0; j < m; j++) {
                if (j == 0) {
                    if (number[j][i] + sum[m - 1][i+1] <= number[j][i] + sum[j][i+1]) {
                        min = number[j][i] + sum[m - 1][i + 1];
                        sign[j][i] = 1;
                        sum[j][i] = min;
                    }
                    else {
                        min = number[j][i] + sum[j][i + 1];
                        sign[j][i] = 0;
                        sum[j][i] = min;
                    }
                    if (min >number[j][i] + sum[j + 1][i+ 1]) {
                        min = number[j][i] + sum[j + 1][i + 1];
                        sign[j][i] = -1;
                        sum[j][i] = min;
                    }
                }
                else if (j == m - 1) {
                    if (number[j][i] + sum[j-1][i + 1] <= number[j][i] + sum[j][i + 1]) {
                        min = number[j][i] + sum[j-1][i + 1];
                        sign[j][i] = 1;
                        sum[j][i] = min;
                    }
                    else {
                        min = number[j][i] + sum[j][i + 1];
                        sign[j][i] = 0;
                        sum[j][i] = min;
                    }
                    if (min > number[j][i] + sum[0][i + 1]) {
                        min = number[j][i] + sum[0][i + 1];
                        sign[j][i] = -1;
                        sum[j][i] = min;
                    }
                }
                else {
                    if (number[j][i] + sum[j -1][i + 1] <= number[j][i] + sum[j][i + 1]) {
                        min = number[j][i] + sum[j - 1][i + 1];
                        sign[j][i] = 1;
                        sum[j][i] = min;
                    }
                    else {
                        min = number[j][i] + sum[j][i + 1];
                        sign[j][i] = 0;
                        sum[j][i] = min;
                    }
                    if (min > number[j][i] + sum[j+1][i + 1]) {
                        min = number[j][i] + sum[j+1][i + 1];
                        sign[j][i] = -1;
                        sum[j][i] = min;
                    }
                }
               
            }
        }
    

    运行结果

    在这里插入图片描述
    在这里插入图片描述

    展开全文
  • 动态规划算法解决流水作业调度

    千次阅读 多人点赞 2020-07-06 11:45:29
    这里写自定义目录标题欢迎使用Markdown编辑器新的改变功能快捷键合理的创建标题,有助于目录的生成如何改变文本的样式插入链接与图片如何插入一段漂亮的代码片生成一个适合...#动态规划算法解决流水作业调度 所展示的欢

    1、问题描述

    有n个作业(编号为1~n)要在由两台机器M1和M2组成的流水线上完成加工。每个作业加工的顺序都是先在M1上加工,然后在M2上加工。M1和M2加工作业i所需的时间分别为ai和bi(1≤i≤n)。
    流水作业调度问题要求确定这n个作业的最优加工顺序,使得从第一个作业在机器M1上开始加工,到最后一个作业在机器M2上加工完成所需的时间最少。可以假定任何作业一旦开始加工,就不允许被中断,直到该作业被完成,即非优先调度。
    输入格式:输入包含若干个用例。每个用例第一行是作业数n(1≤n≤1000),接下来n行,每行两个非负整数,第i行的两个整数分别表示在第i个作业在第一台机器和第二台机器上加工时间。以输入n=0结束。
    输出格式:每个用例输出一行,表示采用最优调度所用的总时间,即从第一台机器开始到第二台机器结束的时间。
    输入样例:
    4
    5 6
    12 2
    4 14
    8 7
    0
    输出样例:
    33

    2、算法分析

    2.1 思路分析如下:

    流水作业调度问题的Johnson算法:
    (1)N1={i|t[i,1]<t[i,2]},N2={i|t[i,1]>=t[i,2]};
    (2)将N1 中作业依t[i,1]的非减序排列;将N2中作业依t[i,2]的非增序排列;
    问题分析:
    当输入的作业数目为4时:
    每个作业在M1上执行的时间为t[i,1],在M2上执行的时间为t[i,2],输入的数据为:
    在这里插入图片描述
    算法按照t[i,1]<t[i,2]先执行的作业,保证M2机器上没有等待,本例中作业1,3满足条件,被选择先执行。当选择第一个作业时,算法选择让M2第一次等待时间最少的那个,本例中作业3的t[i,1]最小,这样就可以让M2第一次等待最少。所以在t[i,1]<t[i,2]的集合中,t[i,1]越小越靠前执行。
    当执行t[i,1]>t[i,2]的作业时,要保证最后一个作业在M2上的执行时间最短,所以作业2,4是按照t[i,2]非增序排列,保证了作业2的t[i,2]是它们两个当中最小的一个。
    算法在计算执行时间的过程如下图所示:
    在这里插入图片描述
    作业执行次序为:3,1,4,2
    1)执行3时:M1上运行4个时间后交给M2,这时M2空闲了4个时间并开始工作。
    所以此时要想将3做完需要18(4+14)个时间。
    2)执行1时:M1上运行5个时间后,M2还在继续运行3,并没有结束。M1结束时间为9,而M2结束1的时间为24,即<9,24>。
    所以此时要想把3,1做完,需要24(6+18)个时间。
    3)执行4时:M1上运行8个时间后,M2还在继续运行3,并没有结束。M1的结束时间为17,而M2结束4的时间为31,即<17,31>
    所以此时要想把3,1,4做完,需要31(7+24)个时间。
    4)执行2时:M1上运行12个时间后,M2还在继续运行4,并没有结束。M1的结束时间为29,而M2结束2的时间为33,即<29,33>.
    所以此时要想把3,1,4,2做完,需要33(2+31)个时间。

    所以,根据运行结果,作业执行时间为33. 作业执行次序为3,1,4,2

    2.2 代码分析流程图如下:

    在这里插入图片描述
    在这里插入图片描述

    2.3 代码如下:

    /*
    1)先执行t[i,1]<t[i,2],保证M2上没有等待。选择第一个作业时,让M2选择第一次等待时间最少的,
    即t[i,1]越小,越靠前执行;
    2)执行t[i,1]>=t[i,2]时,要保证最后一个作业在M2上执行时间最短,所以按照减序排列
    */
    #include<stdio.h>
    #include<string.h>
    #include
    #define N 100
    using namespace std;

    struct node {
    int time;//执行时间
    int index;//作业序号
    bool group;//1代表第一个机器,0代表第二个机器
    };

    bool cmp(node a,node b)
    {//升序排序
    return a.time<b.time;
    }
    int main()
    {
    int i,j,k,n;
    int a[N]={0},b[N]={0};
    int best[N];//最优调度序列
    node c[N];
    scanf("%d",&n);
    for(i=0;i<n;i++) {
    scanf("%d%d",&a[i],&b[i]);
    }
    for(i=0;i<n;i++) { //n个作业中,每个作业的最小加工时间
    c[i].time=a[i]>b[i]?b[i]:a[i];
    c[i].index=i;
    c[i].group=a[i]<b[i];//给符合条件a[i]<b[i]的放入到N1子集标记为true
    }
    sort(c,c+n,cmp);//按照c[]中作业时间增序排序
    j=0,k=n-1;
    for(i=0;i<n;i++) {
    if(c[i].group) { //第一组,从i=0开始放入到best[]中
    best[j++]=c[i].index;//将排过序的数组c,取其中作业序号属于N1的从前面进入,实现N1的非减序排序
    }
    else {
    best[k–]=c[i].index;//将排过序的数组c,取其中作业序号属于N2的从后面进入,实现N2的非增序排序
    }
    }
    j=a[best[0]];//最优调度序列下的消耗总时间,第一个选取M1上的工作时间最少的
    k=j+b[best[0]];
    for(i=1;i<n;i++) {
    j+=a[best[i]];
    k=j<k?(k+b[best[i]]):j+b[best[i]];//消耗总时间的最大值
    }
    printf("%d\n",k);
    for(i=0;i<n;i++) {
    printf("%d “,best[i]+1); //输出最优序列
    }
    printf(”\n");
    return 0;
    }

    2.4 运行结果:

    在这里插入图片描述

    3、时空效率分析

    算法的主要计算时间在对作业集的排序上,在本算法中,我们使用冒泡排序法(sort),因此,在最坏情况下算法所需要计算的时间为O(nlogn)。所需要的空间为O(n)。

    展开全文
  • 图像压缩算法欢迎使用Markdown编辑器新的改变功能快捷键合理的创建标题,有助于目录的生成如何改变文本的样式插入链接与图片如何插入一段漂亮的代码片生成一个适合你的列表创建一个表格设定内容居中、居左、居右...

    图像压缩算法

    #include <iostream>
    #include <string>
    #include<cstdio>
    #include<algorithm>
    using namespace std;
    //计算像素的位数b[i]
    int centbits(int number){
        int sum = 1;
        number = number / 2;
        while(number > 0){
            sum++;
            number = number / 2;
        }
        return sum;
    }
    //计算数组p【】下标从first 到 last的最大位数是多少
    int cent_max_bits(int p[],int first,int last){
        int maxNumber = 0;
        for(int i = first;i < last;i++){
            maxNumber = centbits(p[i]) > maxNumber ? centbits(p[i]) : maxNumber;
        }
        return maxNumber;
    }
    void outPutArray(string s,int i){
        cout<<s<<"["<<i<<"]"<<"=";
    }
    void outPutArrayList(int *p,int n){
        cout<<"p = {";
        for(int i = 0;i<n;i++){
            cout<<p[i];
            if(i != n-1){
                cout<<",";
            }
        }
        cout<<"}"<<endl;;
    }
    
    int main()
    {
        int p[6] = {10,12,15,255,1,2};
        int n = sizeof(p)/sizeof(int);
        //cout<<n<<endl;
        outPutArrayList(p,n);
        int i,j;
        int length[100];
        int bits[100];
        int s[100];
        int m[100]={0};
        /*length[i]存放第i段长度。(L:length)
        bits[i]存放第i段中像素的位数。(B:bits)
        P[i]{P1,P2,···Pn²}以变长格式存储二进制串。*/
        //压缩公式:length[i]*bits[i]+11*m
        int tmp;
        int max_bit;
        s[0] = 0;
        s[1] = cent_max_bits(p,0,1)+11;//b[1]*l[1]+11
        int min_number = 999;
        for(i = 2;i <= n;i++){//分成多少段s[i]段,i = n时,取数列前n个,从i= 2开始,分成2段,取前2个
            outPutArray("s",i);
            cout<<"min{";
            for(j = 0;j < i;j++){
                length[i] = i-j;//存放第i段长度
                max_bit = cent_max_bits(p,j,i);//计算取前i个时最大位数b[i]是多少
                bits[i] = max_bit;
                tmp = s[j] + length[i]*bits[i]+11;//s[i]+l[i]*b[i]+11;
                cout<<"s["<<j<<"]+length["<<length[i]<<"]*bits["<<bits[i]<<"]+11";
                cout<<"|||"<<s[j]+length[i]*bits[i]+11<<"|||";//输出该段压缩空间的值
                if(j != i-1){
                    cout<<",";
                }
                if(min_number >= tmp){
                    min_number = tmp;
                    m[i] = j;
                }
            }
            cout<<"}=";
            s[i] = min_number;
            cout<<s[i]<<endl;
            cout<<endl;
            min_number = 999;
        }
        cout<<"zui xiao kong jian:"<<s[n]<<endl;
        /*for(i = 1;i<=n;i++){
            cout<<m[i]<<" ";
        }*/
        cout<<endl;
    
        //输出像素分段
        int num = 0;
        for(i = 1;i < n;i++){
            if(m[i+1]-m[i] != 0){
                cout<<"di yi duan de xiang su ge shu wei : "<<m[i+1]-m[i]<<"     mei ge xiang su de cun chu shu wei :"<<cent_max_bits(p,num,i-1)<<endl;
                num = i-1;
            }
        }
         cout<<"di yi duan de xiang su ge shu wei : "<<n-m[n]<<"     mei ge xiang su de cun chu shu wei :"<<cent_max_bits(p,num,n)<<endl;
        cout<<"shu chu xu lie:"<<endl;
        //输出最优分段
        int flag=-1;
        int t1 = 1;
        for(i = 1;i <6;i++){
            int account = m[i+1]-m[i];
    
            while(account--){
                    if(t1){
                        cout<<"<";
                        t1 = 0;
                    }
                    flag++;
                    cout<<p[flag];
                    if(account == 0){
                        cout<<">";
                        t1 = 1;
                    }else{
                        cout<<",";
                    }
            }
        }
        cout<<"<";
        for(i = m[n];i<n;i++){
            cout<<p[i];
            if(i != n-1){
                cout<<",";
            }
        }
        cout<<">";
    
    
    }
    
    
    

    在这里插入图片描述

    展开全文
  • 多边形游戏是一个单人玩的游戏,开始时有一个由n个顶点构成的多边形。每个顶点被赋予一个整数值,每条边被赋予一个运算符”+”或”*”。所有边依次用整数从1到n编号。...包括代码+流程图+uml+实验总结
  • 01背包问题 直接copy就能当实验报告… 问题说明 01背包是在M件物品取出若干件放在空间为W的背包里,每件物品的体积为W1,W2至...流程图 算法实现 class Pack: def __init__(self, value, weight): self.value =

    01背包问题

    直接copy就能当实验报告…

    问题说明

    	01背包是在M件物品取出若干件放在空间为W的背包里,每件物品的体积为W1,W2至Wn,与之相对应的价值为P1,P2至Pn。采取怎样的策略能使装入背包的价值最大。
    

    贪心算法

    算法思路

    ​ 计算商品的单位质量价值,并对其进行排序,在不超过背包容量的情况下,选取单位质量价值从高往低装载

    流程图

    在这里插入图片描述

    算法实现
    class Pack:
    
        def __init__(self, value,  weight):
            self.value = value
            self.weight = weight
            self.pValue = value/weight
    
    def greed(goods, maxLoad):
    
        goods.sort(key=lambda x: x.pValue, reverse = True)
    
        load = 0
        tValue = 0
        loaded = []
    
        for each in goods:
            if load < maxLoad:
                tValue += each.value
                load += each.weight
                loaded.append(each)
    
        return tValue, loaded
    
    if __name__ == '__main__':
        n, m= [int(n) for n in input("背包数量和最大承载:").split()]
    
        goods = []
        while n > 0:
            num = [int(n) for n in input().split()]
            good = Pack(num[0], num[1])
            goods.append(good)
            n -= 1
    
        total, loaded = greed(goods, m)
    
        print("total:", total)
        for v in loaded:
            print(v.value)
    
    
    运行样例

    在这里插入图片描述

    算法总结

    ​ 贪心算法往往只能得到问题的局部最优解,最后给出较为接近计算精度要求的最优解。但对诸如最短路径问题、最小生成树问题、哈夫曼编码问题等具有最优子结 构和贪心选择性质的问题却可以获得整体最优解。

    ​ 贪心算法以其简洁、直观著称,对于求解精度要求不很高的问题有着重要意义。

    动态规划算法

    算法思路

    ​ 动态规划算法是将原问题分解为一个个子问题,寻找子问题的最优解,构成员问题的最优解。这是一种自底向上求解算法。使用动态规划的前提是能够找到最优子结构。将最优的子结构存储起来,完成自下而上的递推求解。

    ​ 对于table[i][j],其表示的是前i件物品放入一个容量为j的背包中,可以获得的最大价值。在得到前i-1件商品放入与否的最优解后,进而求解第i件物品的放入与否。

    • 不放入第i件物品,xi= 0,背包中的物品总价值不变,那么原问题可化为“前i-1件物品放入容量为j的背包中”,最大价值为table[i-1][j]

    • 放入第i件物品,xi = 1,背包的总价值增加v[i],此时问题转化为前i-1件物品的最大价值table[i-1][j-w[i]]再加上v[i]的价值

      • 而此时就会有背包的容量是否能装下第i件物品的空间的问题

      table[i][j]={table[i1][j],when j<wimax(table[i1][j],table[i1][jw[i]]+v[i]),when jwi table[i][j] = \begin{cases} table[i-1][j],\quad when\ j < w_i \\ max(table[i-1][j], table[i-1][j-w[i]] + v[i]), \quad when\ j \geq w_i \end{cases}

    复杂度 n2

    流程图

    在这里插入图片描述

    ​ 在实现本题算法执之前,我多次尝试该类动态规划表的填写,并逐渐理解其中的原理

    算法实现
    import numpy as np
    
    if __name__ == '__main__':
        W = 5
        value = [0, 12, 10, 20, 15]
        weight = [0, 2, 1, 3, 2]
        table = np.zeros((5, W+1))
    
        for i in range(1, 5):
            for j in range(1, 6):
                if((j-weight[i]) < 0):
                    continue
                table[i][j] = max(table[i-1][j-weight[i]] + value[i], table[i-1][j])
    
        print(table[4, 5])
    
    运行样例

    在这里插入图片描述

    算法总结

    ​ 一般来说动态规划算法只要设计得当,效率往往是很高的,在时间上溢出的可能性不大,但是由于动态规划需要记录大量的中间过程,对内存空间的需求较大,设计不合理很有可能导致内存的溢出。

    ​ 动态规划广泛地运用于生物信息学中,诸如序列比对,蛋白质折叠,RNA结构预测和蛋白质-DNA结合等任务。

    回溯法

    算法思想

    01背包需要用回溯法构造解的子集树。对于每一个物品i,对于该物品只有选与不选2个决策,总共有n个物品,可以顺序依次考虑每个物品,这样就形成了一棵解空间树。

    ​ 基本思想就是遍历这棵树,以枚举所有情况。对于在该子集树中每个节点处进行选与不选的决策,如果剩余空间能容下当前物品则将其装入,并搜索左子树;如果不装入当前物品,且满足限界条件(剩余物品价值与当前价值的总和大于最优解)就搜索其右子树。这里左右子树并不冲突,只是当且仅当满足约束条件时才可以装入,而不管是否满足约束条件都会进行限界条件的判断。

    流程图

    在这里插入图片描述

    算法实现
    import numpy as np
    
    weight = [0, 2, 5, 4, 2]
    value = [0, 6, 3, 5, 4]
    flag = np.full(len(value), False)
    W = 10
    bestV = 0
    bestX = flag
    cv = 0
    cw = 0
    
    def back(k):
        global maxV, cv, cw, bestV
    
        if k >= len(value):
            if cv > bestV:
                for i in range(1, len(value)):
                    bestX[i] = flag[i]
    
                bestV = cv
    
                return
    
        if cw + weight[k] <= W:    #判断左子树是否符合条件
            flag[k] = True
            cw += weight[k]
            cv += value[k]
            back(k+1)
            cv -= value[k]
            cw -= weight[k]
    
        if (bound(k+1, cv) > bestV):   #右子树
            flag[k] = False
            back(k+1)
    
    
    def bound(k, cv):
        rv = 0
    
        while(k < len(value)):
            rv += value[k]
            k += 1
    
        return cv + rv
    
    if __name__ == '__main__':
        back(1)
        print(bestV)
    
    运行样例

    在这里插入图片描述

    算法总结

    ​ 回溯法从本质上看,就是一种深度优先搜索的试探算法,寻找最优或者符合条件的解。

    ​ 回溯法和穷举法有些类似,它们都是基于试探的。区别时穷举法需要将一个解的各个部分全部生成后才检查是否满足条件,不满足则完全放弃该解进而尝试其他的解。这时回溯法的好处就体现出来了,它的解时一步步生成的,在当前解不满足条件时会回退一步去求解,而且回溯法对解空间进行了限界对于结果是否符合条件进行预判,降低时间成本。

    分支限界法(FIFO)

    算法思想

    ​ 物品放入背包中或物品不放入背包中,根据约束条件舍去无效情况。当前物品k放入背包中时,获取当前最大总价值,下一个物品k+1也存在放入背包和不放入背包中两个节点。当物品k不放入背包时,上个节点的最总价值为当前节点的最总价值,下一个物品k+1仍然存在放入背包和不放入背包两个节点。对于物品k+1以此类推,最终根据不同的放入情况选择一个最优解作为可以放入背包物品的最大总价值。

    ​ 该算法为队列法分支限界法。

    算法模拟

    在这里插入图片描述

    ​ 第一次实验时,对回溯法和分支限界法较为生疏,所以在纸上对其进行了多次模拟,并经过调试最终写出了算法。

    算法实现
    import java.util.LinkedList;
    import java.util.Queue;
    import java.util.Scanner;
    
    public class ZeroAndOne {
        static int N = 10;
        static Goods[] goods = new Goods[N];
        static boolean[] bestX = new boolean[N];
        static int bestP, W, n, sumW, sumV; //bestP最优值,W为容量, n为物品数
                                            //sumW所有物品的总重量,sumV总价值
    
        public static void main(String[] args) {
    
            Scanner scanner = new Scanner(System.in);
            System.out.print("n:");
            n = scanner.nextInt();
            System.out.print("W:");
            W = scanner.nextInt();
            bestP = 0;
            sumW = 0;
            sumV = 0;
    
            System.out.printf("w, v:");
            for (int i = 1; i <= n; i++) {
    
                int weight = scanner.nextInt();
                int value = scanner.nextInt();
                Goods good = new Goods(weight, value);
                goods[i] = good;
    
                sumW += goods[i].weight;
                sumV += goods[i].value;
            }
    
            if (sumW <= W) {
                bestP = sumV;
                System.out.println("全放,价值:" + bestP);
            } else {
                bfs();
                System.out.println("bestP:" + bestP);
    
                System.out.println("these:");
                for (int i = 1; i <= n; i++) {
                    if (bestX[i]) {
                        System.out.print(i + " ");
                    }
                }
            }
        }
    
        static class Node {
            int cp;      //当前总价值
            int rp;      //剩余物品的总价值
            int rw;      //背包剩余容量
            int id;      //物品号
    
            boolean []x = new boolean[N];
    
            public Node(int cp, int rp, int rw, int id) {
                this.cp = cp;
                this.rp = rp;
                this.rw = rw;
                this.id = id;
            }
        }
    
        static class Goods {
    
            int weight;
            int value;
    
            public Goods(int weight, int value) {
                this.weight = weight;
                this.value = value;
            }
        }
    
        public static int bfs() {
    
            int t, tcp, trp, trw;
            /**
             * t 当前物品序号
             * tcp 当前cp trp  trw同
             */
    
            Queue<Node> myQueue=new LinkedList<>();
            myQueue.add(new Node(0, sumV, W, 1));
    
    
            while (!myQueue.isEmpty()) {
    
                Node liveNode = new Node(0, 0, 0, 0);
                Node lChild = new Node(0, 0, 0, 0);
                Node rChild = new Node(0, 0, 0, 0);
    
                liveNode = myQueue.poll();
                t = liveNode.id;
    
                //如果为最后一个节点就不再搜索,没有剩余容量也不再搜索
                if (t > n || liveNode.rw == 0) {
    
                    if (liveNode.cp >= bestP) {
                        for (int i = 1; i <= n; i++) {
                            bestX[i] = liveNode.x[i];
                        }
    
                        bestP = liveNode.cp;
                    }
    
                    continue;
                }
    
                //不满足条件不再搜索
                if (liveNode.cp + liveNode.rp < bestP) {
                    continue;
                }
    
                tcp = liveNode.cp;
                trp = liveNode.rp - goods[t].value;   //不管当前商品是否装入,剩余价值都会减少
                trw = liveNode.rw;
    
                //满足约束条件,放入背包
                if (trw >= goods[t].weight) {
    
                    lChild.rw = trw - goods[t].weight;
                    lChild.cp = tcp + goods[t].value;
                    lChild = new Node(lChild.cp, trp, lChild.rw, t+1);
    
                    for (int i = 1; i < t; i++) {
                        lChild.x[i] = liveNode.x[i];
                    }
    
                    lChild.x[t] = true;
                    if (lChild.cp > bestP) {
                        bestP = lChild.cp;
                    }
    
                    myQueue.add(lChild);
                }
    
                //右孩子
                if (tcp + trp >= bestP) {
                    rChild = new  Node(tcp, trp, trw, t+1);
    
                    for (int i =1; i < t; i++) {
                        rChild.x[i] = liveNode.x[i];
                    }
                    rChild.x[t] = false;
                    myQueue.add(rChild);
                }
            }
    
            return bestP;
        }
    }
    
    运行样例
    回溯与分支限界
    • 共同点:一种在问题的解空间树上搜索问题解的算法。
    运行样例

    在这里插入图片描述

    回溯与分支限界
    • 共同点:一种在问题的解空间树上搜索问题解的算法。
    • 不同点:求解目标不同,回溯法的目标是找出解空间树满足约束条件的所有解,而分支限界法的求解目标是尽快地找出满足约束条件的一个解;搜索方法不同,回溯法采用深度优先方法搜索解空间,而分支限界法一般采用广度优先或以最小消耗优先的方式搜索解空间树;对扩展结点的扩展方式不同,回溯法中,如果当前的扩展结点不能够再向纵深方向移动,则当前扩展结点就成为死结点,此时应回溯到最近一个活结点处,并使此活结点成为扩展结点。分支限界法中,每一次活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点,就一次性产生其所有儿子结点;存储空间的要求不同,分支限界法的存储空间比回溯法大得多,当内存容量有限时,回溯法成功的可能性更大。
    展开全文
  • 字符串匹配算法-动态规划之 KMP 算法详解欢迎使用Markdown编辑器新的改变功能快捷键合理的创建标题,有助于目录的生成如何改变文本的样式插入链接与图片如何插入一段漂亮的代码片生成一个适合你的列表创建一个表格...
  • 哈工程本科算法实验-0-1背包(动态规划-分支限界-回溯法)【数据+代码+说明+流程图+测试用例】
  • 文章目录动态规划(dynamic programming)DP四步骤DP基本要素最长公共子序列(longest common sequence)如何改变文本的样式插入链接与图片如何插入一段漂亮的代码片生成一个适合你的列表创建一个表格设定内容居中、居左...
  • 动态规划——多段(简单实现)

    千次阅读 2019-09-23 22:40:42
    虽然花了一定时间,但还是有点收获,对动态规划有了更深的理解。现在把思考过程分享出来与君共勉。 首先贴出来参考书上的多段(图片来源https://blog.csdn.net/ncepuzhuang/article/details/8923790) 有关书上...
  • 动态规划

    2019-12-26 20:12:54
    基础算法简介前提算法分类回溯法动态规划递归和分治贪心算法分支界限法如何插入一段漂亮的代码片生成一个适合你的列表创建一个表格设定内容居中、居左、居右SmartyPants创建一个自定义列表如何创建一个注脚注释也是...
  • 机器人路径规划动态窗口法

    千次阅读 2020-03-19 17:56:56
    动态窗口法(Dynamic Window Approach)概述 DWA是一种基于速度的局部规划器,可计算达到目标所需的机器人的最佳无碰撞...流程图如下: 以下代码参考:https://github.com/AtsushiSakai/PythonRobotics 初始化机器...
  • 目录什么是算法算法的特征衡量算法的方式常用算法排序算法查找算法深度优先算法广度优先算法动态规划算法贝叶斯分类算法压缩算法加密算法图形渲染算法 什么是算法 算法是完成某一特定任务的过程,通常使用数据结构...
  • 我对背包问题的看法 ...对于这个选取,我喜欢举一个小栗子,通过流程图,直观的看出细节 一些小栗子 Lintcode 92 背包问题1 class Solution: #d[j]表示当size等于j时,最多能承重的大小 def backPack(self, m, A):
  • Bellman-Ford算法

    2017-07-10 17:23:14
    求解单源最短路问题: ... Bellman, 动态规划的提出者)和小莱斯特•福特(Lester Ford)发明。Bellman-Ford算法流程如下: 给定G(V, E)(其中V、E分别为G的顶点集与边集),源点s, 数组Dist
  • 的分解 :图形中的路径 贪婪算法动态编程 :线性规划和归约 :NP完全问题 :处理NP完整性 量子算法 工作流程 通过] add Revise安装Revise.jl 。 在项目目录中启动Julia REPL会话,并通过] activate "."使用...

空空如也

空空如也

1 2 3 4 5 ... 7
收藏数 138
精华内容 55
关键字:

动态规划算法流程图