精华内容
下载资源
问答
  • 动态规划法求最大子段和问题C++
    千次阅读
    2020-05-20 09:39:30

    动态规划法求最大子段和问题

    给定由n个整数组成的序列(a1, a2, …, an),求该序列形如(ai, ai+1, ai+2,…, ai+n) 的子段和的最大值,当所有整数均为负整数时,其最大子段和为0。依此定义,所求的最优值为:
    图片太美,无法描述
    动态规划法代码如下:

    #include <iostream>
    #include <stdlib.h>
    
    using namespace std;
    
    int *maxSum(int a[], int b[], int len){
        int *index;
        int i;
        index = (int*)malloc(sizeof(int)*3);    //申请空间
        b[0] = a[0];    //b[0]初始化,将a[0]赋值给b[0]
        index[0] = b[0];    //假设b[0]是最大子段和
        index[1] = index[2] = 1;    //起始位置的逻辑位置为1
    
        for(i=1; i<len; i++){
            if(b[i-1]>0){   //
                b[i] = b[i-1]+a[i];
            }
            else{   //如果前段和为非正数,舍去,重新寻找子序列
                b[i] = a[i];
                index[1] = i+1; //存储最大子段和左端元素的序数
            }
            if(b[i]>index[0]){
                index[0] = b[i];    //存储最大子段和的值
                index[2] = i+1;     //存储最大子段和右端元素的序数
            }
        }
        return index;
    }
    
    int main()
    {
        int *max;
        int a[6] = {-20, 11, -4, 13, -5, -2};
        int b[6];
    
        max = maxSum(a, b, 6);
    
        cout << "The largest subsection sum is:" << max[0] << endl;
        cout << "Start at:" << max[1] << endl;
        cout << "End at:" << max[2] << endl;
    
        return 0;
    }
    
    
    更多相关内容
  • 动态规划解步骤】 第一步,刻画问题的最优解子结构。可以将背包问题的求解过程看作是进行一系列的决策过程,即决定哪些物品应该放入背包,哪些物品不放入背包。如果一个问题的最优解包含了物品n,即xn=1,那么其余...

    1.实验内容
    0-1背包问题:若有物品n个,每个物品的价值Value,用vi表示,每个物品的重量weight用wi表示,其中vi和wi均为非负数。设背包的总容量为W,且W为非负数。现需要考虑的问题是:如何选择装入背包的物品,使装入背包的物品总价值最大。

    【动态规划解步骤】
    第一步,刻画问题的最优解子结构。可以将背包问题的求解过程看作是进行一系列的决策过程,即决定哪些物品应该放入背包,哪些物品不放入背包。如果一个问题的最优解包含了物品n,即xn=1,那么其余x1,x2,…,x(n-1)一定构成子问题1,2,…,n-1在容量W-wn时的最优解。如果这个最优解不包含物品n,即xn=0,那么其余x1,x2,…,x(n-1)一定构成子问题1,2,…,n-1在容量W时的最优解。

    第二步,递归定义最优解的值,根据上述分析的最优解的结构递归地定义问题最优解。设G[i,w]表示背包容量为w时,i个物品导致的最优解的总价值,得到下式。显然要求G[n,w]:
    在这里插入图片描述

    2.算法流程图及说明
    在这里插入图片描述

    3.核心代码解释

    /*
    c[i][w]表示背包容量为w时,i个物品导致的最优解的总价值,大小为(n+1)*(w+1)
    v[i]表示第i个物品的价值,大小为n
    w[i]表示第i个物品的重量,大小为n
    */
    #include <iostream>
    using namespace std;
    void Dny(int n, int W, int c[][18], int* v, int* wei)//构建最优解子结构
    {
    	memset(*c, 0, (W + 1) * sizeof(int));
    	for (int i = 1; i <= n; i++)//构建最优子结构从装入一个物品开始
    	{
    		c[i][0] = 0;
    		for (int w = 1; w <= W; w++)
    		{
    			if (wei[i - 1] > w)	//此处比较是关键,当当前第一个物品重量大于当前背包容量时,最优子结构等于上一所装数量的最优解
    			{
    				c[i][w] = c[i - 1][w];
    			}
    			else//否则可以装入
    			{
    				int temp = c[i - 1][w - wei[i - 1]] + v[i - 1];	//注意wei和v数组中的第i个应该为wei[i-1]和v[i-1]
    				if (c[i - 1][w] > temp)//如果上一个最优子结构大于当前价值,则不装,否则装入。
    				{
    					c[i][w] = c[i - 1][w];
    				}
    				else
    					c[i][w] = temp;//写入当前最优解
    			}
    		}
    	}
    }
    
    void assign(int c[][18], int* x, int* wei, int n, int W)
    {
    	int w = W;
    	for (int i = n; i >= 2; i--)
    	{
    		if (c[i][w] == c[i - 1][w])
    		{
    			x[i - 1] = 0;
    		}
    		else
    		{
    			x[i - 1] = 1;
    			w = w - wei[i - 1];
    		}
    	}
    	if (c[1][w] == 0)
    		x[0] = 0;
    	else
    		x[0] = 1;
    }
    
    int main()
    {
    	int n = 5;
    	int W = 17;
    	int w[] = { 3, 4, 7, 8, 9 };
    	int v[] = { 4, 5, 10, 11, 13 };
    	int c[6][18] = { 0 };
    	Dny(n, W, c, v, w);
    	cout << c[5][17] << endl;
    	int x[5];
    	assign(c, x, w, n, W);
    	cout << "Here is the assignment!" << endl;
    	for (int i = 0; i < n; i++)
    		cout << x[i] << endl;
    	for (i = 0; i <= n; i++)
    	{
    		for (int j = 0; j <=W; j++)
    			cout << c[i][j] << "   ";
    		cout << endl;
    	}
    	return 0;
    }
    

    }
    4.测试数据及截图
    测试jietu
    主要是写出这个函数在这里插入图片描述程序中表示出来:

    if (wei[i - 1] > w)	
    	c[i][w] = c[i - 1][w];
    else
    	int temp = c[i - 1][w - wei[i - 1]] + v[i - 1];
    

    然后构建表格!当运行到装下一个物品的时候,判断上一个物品是放着还是取出!

    展开全文
  • 本压缩文档包含三个文件:用动态规划法解决TSP问题可执行源代码,word文档报告,实验测试数据
  • 动态规划算法-多边形游戏。回溯-符号三角形问题。贪心算法-计算加油次数。包括流程图+代码+实验结果截屏+实验总结。
  • 算法(七):图解动态规划

    千次阅读 2018-09-24 17:37:10
    动态规划实质是分治以及解决冗余,将各个子问题的解保存下来,让后面再次遇到的时候可以直接引用,避免重复计算,动态规划的显著特征之一,会有大量的子问题重复,可以直接使用前面的解 贪心算法的每一次...

    算法简介

    动态规划,将大问题划分为小问题进行解决,从而一步步获取最优解的处理算法

    与贪婪算法区别

    • 2者都是将大问题划分为规模更小的子问题

    • 动态规划实质是分治法以及解决冗余,将各个子问题的解保存下来,让后面再次遇到的时候可以直接引用,避免重复计算,动态规划的显著特征之一,会有大量的子问题重复,可以直接使用前面的解

    • 贪心算法的每一次操作都对结果产生直接影响(处理问题的范围越来越小),而动态规划则不是。贪心算法对每个子问题的解决方案都做出选择,不能回退;动态规划则会根据以前的选择结果对当前进行选择,有回退功能(比如背包问题,同一列相同容量的小背包越往后才是最优解,推翻前边的选择)。动态规划主要运用于二维或三维问题,而贪心一般是一维问题

    • 贪婪算法结果是最优近似解,而动态规划是最优解

    • 动态规划类似搜索或者填表的方式来,具有最优子结构的问题可以采用动态规划,否则使用贪婪算法

    案例

    这边的案例来自"算法图解"一书

    案例一

    背包问题:有一个背包,容量为4磅 , 现有如下物品

    物品重量价格
    吉他(G)11500
    音响(S)43000
    电脑(L)32000

    要求达到的目标为装入的背包的总价值最大,并且重量不超出。

    类似问题在前边""贪婪算法"一文介绍了求出近似解,现在使用动态规划求出最优解。

    解决类似的问题可以分解成一个个的小问题进行解决,假设存在背包容量大小分为1,2,3,4的各种容量的背包(分配容量的规则为最小重量的整数倍):

    例如:

    物品1磅2磅3磅4磅
    吉他(G)    
    音响(S)    
    电脑(L)    

    对于第一行(i=1), 目前只有吉他可以选择,所以

    物品1磅2磅3磅4磅
    吉他(G)1500(G)1500(G)1500(G)1500(G)
    音响(S)    
    电脑(L)    

    对于第二行(i=2),目前存在吉他和音响可以选择,所以

    物品1磅2磅3磅4磅
    吉他(G)1500(G)1500(G)1500(G)1500(G)
    音响(S)1500(G)1500(G)1500(G)3000(S)
    电脑(L)    

    对于第三行(i=3),目前存在吉他和音响、电脑可以选择,所以

    物品1磅2磅3磅4磅
    吉他(G)1500(G)1500(G)1500(G)1500(G)
    音响(S)1500(G)1500(G)1500(G)3000(S)
    电脑(L)1500(G)1500(G)2000(L)3500(L+G)

    以上的都符合公式:

    F(i,j) = max{ F(i-1,j), W(i) + F(i,j = j-V(i))} 
    即max{上面一个单元格的值, 当前商品的价值 + 剩余空间的最大价值}
    
    F(i,j)的代表 i行j列可以获得的最大价值,W(i)代表该行物品的价值,V(i)在此处代表该行物品所占据的空间重量,
    F(i,j = j-V(i)) : 假设
    复制代码

    比如F(3,4) = max{ F(2,4), F(3,3) + 2000 } = max { 3000, 1500 + 2000} = 3500, 该问题的时间复杂度O(V*N),V位背包容量,N为物品总数,即表格格子总数。

    上述背包空间的划分依据一般根据最小的物品所占的大小整数倍进行划分(这边是吉他,占据1磅),假设多了个0.5磅的东西则,需要划分为更细的粒度(0.5,1,1.5,2,2.5,3,3.5,4)

    并且会发飙沿着一列往下走时,最大价值不会降低,因为每次计算迭代时,都选取的最大值。并且结果与行的顺序并无关系,比如更换为:

    使用上述公式计算,当背包为4磅,可装入的最大价值依旧为 3500:

    物品1磅2磅3磅4磅
    音响(S)   3000(S)
    电脑(L)  2000(L)3000(S)
    吉他(G)1500(G)1500(G)2000(G)3500(L+G)

    计算过程:

    i=1: (1,1)、(1,2)、(1,3) : 因为 j=1,2,3时 < (V(i) = 4) 所以装不下,置空 (1,4) : max{ F(i-1,j), W(i) + F(i,j-V(i))} = max{ F(0,4),3000 + F(1,0)} = 3000

    i=2: (2,1)、(2,2) : 因为 j=1,2时 < (V(i) = 4、V(i-1)=3) 所以装不下,置空 (2,3): max{ F(1,3), W(2) + F(2,0)} = 2000 (2,4): max{ F(1,4), W(2) + F(2,1)} = max{ 3000, 2000 + 0} = 3000

    i=3: (3,1) : max{ F(2,1), 1500 + F(3,0)} = 1500 (3,2) : max{ F(2,2), 1500 + F(3,1)} = 1500 (因为吉他只有一把,无法重复放入) (3,3) : max{ F(2,3), 1500 + F(3,2)} = max{2000,1500} = 2000 (因为吉他只有一把,无法重复放入) (3,4) : max{ F(2,4), 1500 + F(3,3)} = max{3000,3500} = 3500

    案例二

    旅游行程最优化:

    假设有2天的时间,想要去如下地方旅游,如何好好利用,使得总评分高:

    名胜时间评分
    伦敦教堂(A)0.5天7
    伦敦剧场(B)0.5天6
    伦敦美术馆(C)1天9
    伦敦博物馆(D)2天9
    伦敦运动馆(E)0.5天8

    该问题其实也是一个背包,只是容量变成了时间,处理方式同上,很快便可以得出:

    F(i,j) = max{ F(i-1,j), W(i) + F(i,j-V(i))} 即max{上面一个单元格的值, 当前商品的价值 + 剩余空间的价值}
    
    F(i,j)的代表 i行j列可以获得的最大价值,W(i)代表该行物品的价值,V(i)在此处代表该行物品所占据的空间重量
    复制代码
    名胜0.5天1天1.5天2天
    伦敦教堂(A)7(A)7(A)7(A)7(A)
    伦敦剧场(B)7(A)13(A+B)13(A+B)13(A+B)
    伦敦美术馆(C)7(A)13(A+B)16(A+C)22(A+B+C)
    伦敦博物馆(D)7(A)13(A+B)16(A+C)22(A+B+C)
    伦敦运动馆(E)8(E)15(A+E)21(A+B+E)24(A+C+E)

    局限性

    动态规划的局限性之一便是每次处理时,考虑的是整件物品进行处理,无法支持拿走几分之几的做法,比如案例一修改为:

        背包4磅,1.有一整袋10磅的燕麦,每磅6美元 ; 
                     2.有一整袋10磅的大米,每磅3美元 ; 
                     3.有一整袋10磅的土豆,每磅5美元 ; 
            
            因为整袋无法装入,情况不再是要么拿要么不拿,而是打开包装拿物品的一部分,这种情况下动态规划就无法处理。动态规划只适合于整件物品处理的情况。但使用前面介绍的贪婪算法则很合适,一个劲拿最贵的,拿光后再拿下一个最贵。
    复制代码

    动态规划的局限性之二便是无法处理相互依赖的情况,比如案例二中,增加想要去的3个地点

    名胜时间评分
    巴黎铁塔(F)1.5天8
    巴黎大学(G)1.5天9
    巴黎医院(H)1.5天7
    从这些地方还需要很长时间,因为得从伦敦前往巴黎,这需要0.5天时间(1.5天包含了0.5天的路程消耗)。如果这3个地方都去的话,是总的需要1.5 * 3= 4.5天? 其实并不是,到达巴黎后,连续玩这3个地方其实只需 1.5 + 1 + 1 = 3.5天。 这种将 "巴黎铁塔"装入"背包"会使得"巴黎大学"、"巴黎医院"变便宜的情况,无法使用动态规划来进行建模。
    复制代码

    动态规划功能虽然强大,能够解决子问题并使用这些答案来解决大问题。但仅当每个子问题都是离散的,即不依赖于其它子问题时,动态规划才管用。

    java实现

    案例一:
    
    /**
     * 动态规划 - 简单背包问题
     * @author Administrator
     *
     */
    public class KnapsackProblem {
    	
    	public static void main(String[] args){
    
    		float knapsackWeight = 4;
    		float[] itemsWeights = new float[] {1, 4, 3};
    		float[] itemsPrices = new float[] {1500, 3000, 2000}; 
    		float[][] table = knapsackSolution(knapsackWeight, itemsWeights, itemsPrices);
    		
    		for (int line = 0; line < table.length; line++ ) {
    			System.out.println("-----------------line =" + line);
    			for (int colume = 0; colume < table[line].length; colume++ ) {
    				System.out.println(table[line][colume] + ",");
    			}
    		}
    	}
    	
    	/**
    	 * 
    	 * @param knapsackWeight 背包总容量
    	 * @param itemsWeights	  各个物品的所占据的容量
    	 * @param itemsPrices	  各个物品所具有的价值	
    	 * @return
    	 */
    	public static float[][] knapsackSolution(float knapsackWeight, float[] itemsWeights, float[] itemsPrices) {
    		if (itemsWeights.length != itemsPrices.length) {
    			throw new IllegalArgumentException();
    		}
    		
    		//计算表格的行数 --物品数量
    		int lines = itemsPrices.length;
    		//计算出划分的背包最小的空间,即表格每一列代表的重量为  column * minWeight
    		float minWeight = getMinWeight(itemsWeights);
    		//计算表格的列数 --分割出的重量数目
    		int colums = (int) (knapsackWeight/minWeight);
    		System.out.println("lines = " + lines + ",colums = " + colums + ",minWeight = " + minWeight);
    		//创建表格对象,lines行colums列
    		float[][] table = new float[lines][colums];
    	
    		for (int line = 0; line < lines; line++ ) {
    			for (int colume = 0; colume < colums; colume++ ) {
    				
    				float left = table[(line - 1) < 0 ? 0 : (line - 1) ][colume];
    				float right = 0;
    				//判断当前划分的小背包是否可以装下该物品,当前背包容量为(colume +1)*minWeight
    				if ((colume +1)*minWeight >= itemsWeights[line]) {
    					//获取当前背包剩余空间
    					float freeWeight = ((colume+1)*minWeight - itemsWeights[line]);
    					//判断剩余空间是否还可以装下其它的东西
    					int freeColumn = (int) (freeWeight/minWeight) - 1;
    					if (freeColumn >= 0 && line > 0) {
    						//因为表格上同一列的位置上,越往下价值越高,所以这边直接取的上一行的freeColumn位置就行
    						right = itemsPrices[line] + table[line - 1][freeColumn];
    					}else {
    						right = itemsPrices[line];
    					} 	
    				}
    
    				table[line][colume] = Math.max(left, right);
    			}
    			
    		}
    		return table;
    		
    	}
    	
    	/**
    	 * 获取所有物品中最小的重量
    	 * 
    	 * @param itemsWeights 各个物品的所占据的容量
    	 * @return
    	 */
    	public static float getMinWeight(float[] itemsWeights) {
    		float min = itemsWeights[0];
    		
    		for (float weight : itemsWeights) {
    			min = min > weight ? weight : min;
    		}
    		//保留最多2位小数,并默认非零就进位1.222 --> 1.23
    		//为啥String.valueOf,参照https://www.cnblogs.com/LeoBoy/p/6056394.html
    		return new BigDecimal(String.valueOf(min)).setScale(2, RoundingMode.UP).floatValue();
    	}
    	
    }
    复制代码
    执行完main方法打印信息如下:
    lines = 3,colums = 4,minWeight = 1.0
    -----------------line =0
    1500.0,
    1500.0,
    1500.0,
    1500.0,
    -----------------line =1
    1500.0,
    1500.0,
    1500.0,
    3000.0,
    -----------------line =2
    1500.0,
    1500.0,
    2000.0,
    3500.0,
    复制代码

    简单修改为,即为案例二的实现代码: float knapsackWeight = 2; float[] itemsWeights = new float[] {0.5f,0.5f,1,2,0.5f}; float[] itemsPrices = new float[] {7,6,9,9,8};

     

    展开全文
  • 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件物品的空间的问题

      t a b l e [ i ] [ j ] = { t a b l e [ i − 1 ] [ j ] , w h e n   j < w i m a x ( t a b l e [ i − 1 ] [ j ] , t a b l e [ i − 1 ] [ j − w [ i ] ] + v [ i ] ) , w h e n   j ≥ w i 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} table[i][j]={table[i1][j],when j<wimax(table[i1][j],table[i1][jw[i]]+v[i]),when jwi

    复杂度 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;
        }
    }
    
    运行样例
    回溯与分支限界
    • 共同点:一种在问题的解空间树上搜索问题解的算法。
    运行样例

    在这里插入图片描述

    回溯与分支限界
    • 共同点:一种在问题的解空间树上搜索问题解的算法。
    • 不同点:求解目标不同,回溯法的目标是找出解空间树满足约束条件的所有解,而分支限界法的求解目标是尽快地找出满足约束条件的一个解;搜索方法不同,回溯法采用深度优先方法搜索解空间,而分支限界法一般采用广度优先或以最小消耗优先的方式搜索解空间树;对扩展结点的扩展方式不同,回溯法中,如果当前的扩展结点不能够再向纵深方向移动,则当前扩展结点就成为死结点,此时应回溯到最近一个活结点处,并使此活结点成为扩展结点。分支限界法中,每一次活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点,就一次性产生其所有儿子结点;存储空间的要求不同,分支限界法的存储空间比回溯法大得多,当内存容量有限时,回溯法成功的可能性更大。
    展开全文
  • 动态规划法求解TSP问题 C++

    千次阅读 热门讨论 2020-04-25 13:25:09
    //创建动态数组,节省空间 int **arc = new int*[n];//的代价矩阵 for (i = 0; i ; i++) arc[i] = new int[n]; int **d = new int*[n];//存放迭代结果,即过程矩阵,过程表 for (i = 0; i ; i++) d[i] =...
  • 栅格法一般作为路径规划的环境建模技术来用,作为路径规划的方法它很难解决复杂环境信息的问题,一般需要与其他智能算法相结合。
  • 跟以往的动态规划解题思路相同,要求A1~A5的连乘,就先求A1A2的,再求A1A2A3的… 我们需要填写下列这张表,它记录了每个子问题的值 按照上的填写思路,我们最终填完所有的表,即下的左表。 而下的右侧表格...
  • 动态规划】图像压缩问题

    千次阅读 多人点赞 2019-10-15 17:24:54
    这里写自定义目录标题动态规划之图像压缩问题问题描述最优子结构最优子结构的性质插入链接与图片如何插入一段漂亮的代码片生成一个适合你的列表创建一个表格设定内容居中、居左、居右SmartyPants创建一个自定义列表...
  • 机器人路径规划动态窗口

    千次阅读 2020-03-19 17:56:56
    动态窗口(Dynamic Window Approach)概述 DWA是一种基于速度的局部规划器,可计算达到目标所需的机器人的最佳无碰撞...流程图如下: 以下代码参考:https://github.com/AtsushiSakai/PythonRobotics 初始化机器...
  • 这是一道经典的动态规划问题. 此题目中,你将会看到动态规划全局最优解的体现。以及常见动态规划解题思路总结。 零钱兑换 给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需...
  • 了解动态规划 有向传递闭包的计算-warshall算法 传递闭包的具体计算过程图解 warshall算法的核心内容 算法的求解过程 伪代码 具体代码实现 #include<bits/stdc++.h> #include<stdio.h> #...
  • 算法-动态规划 Dynamic Programming--从菜鸟到老鸟

    万次阅读 多人点赞 2017-07-15 22:58:29
    前言最近在牛客网上做了几套公司的真题,发现有关动态规划(Dynamic Programming)算法的题目很多。相对于我来说,算法里面遇到的问题里面感觉最难的也就是动态规划(Dynamic Programming)算法了,于是花了好长时间...
  • 动态规划法(五)——多段问题

    万次阅读 2017-04-11 14:36:35
    给定一个多段,求出多段中的最短路径和最短路径长度。 什么是多段? 多段是一个有向、无环、带权 。 有且仅有一个起始结点(原点source) 和 一个终止结点(汇点target)。 它有n个阶段,每个阶段由特定...
  • 给定n种物品和一背包。物品i的重量是wi,其价值为vi,背包的容量为C。问应如何选择装入背包的物品,使得装入背包中物品的总价值最大?...0-1背包问题是一个特殊的整数规划问题。 最优子结构性质 ...
  • 常用十大算法_动态规划算法(DP)

    千次阅读 2020-07-25 08:33:16
    动态规划算法(DP) 高能预警:DP算法不容易理解,需要动脑筋+查资料+找例题 动态规划算法(Dynamic Programming),是将复杂问题拆分成子问题,并在子问题的基础上,求解复杂问题,子问题之间不是独立的,而是...
  • 算法学习(动态规划)- 数塔问题

    千次阅读 2020-11-28 17:58:21
    想想或许是鸡蛋问题对我现在而言难了一些,所以只好找了一些其它的动态规划问题,从简单入手,先去理解“动态规划”的思想精髓,再反过来去思考“鸡蛋问题”。 其中一个经典问题是01背包问题,这是我之前一直想搞懂...
  • 哈工程本科算法实验-0-1背包(动态规划-分支限界-回溯)【数据+代码+说明+流程图+测试用例】
  • 动态规划法,C语言编写的解决最大字段和的问题
  • 矩阵连乘(动态规划算法)

    千次阅读 2020-10-10 10:13:34
    (p[i-1] * p[i] * p[j]:最后两个矩阵的计算量) 动态规划算法代码: #include #include using namespace std; const int L = 7; int matrixMultiple(int n, vector< vector<int> > &m, vector< vector<int> > &s,...
  • 数塔问题——动态规划求解(C++)

    千次阅读 2020-11-29 18:41:47
    实现思想:动态规划 5 9 12 15 10 6 8 2 18 9 5 19 7 10 4 16 以上是输入样例。 MAX=59 9->12->10->18->10 以上是输出样例。 C++代码: #include<iostream> using namespace std; int main() ...
  • 动态规划 最长公共子序列 过程图解

    万次阅读 多人点赞 2016-05-29 22:54:25
    1.基本概念  首先需要科普一下,最长公共子序列(longest common sequence)和最长公共子串(longest common substring)不是一回事儿。什么是子序列呢?即一个给定的序列的子...给一个再解释一下:  如
  • 动态规划求解收集硬币的问题(‘超’详细介绍) 在m*n的方格中放有一些硬币,每格的硬币数目最多为一个,从木板左上方开始收集尽可能多的硬币并把它们带到右下方的单元格。每一步只可以从当前的位置向右移动一格或向...
  • 目录1动态规划思想2适用场景3例题分析3.1示例1:42.接雨水 1动态规划思想 2适用场景 3例题分析 3.1示例1:42.接雨水 题目描述 给定 n 个非负整数表示每个宽度为 1 的柱子的高度,计算按此排列的柱子,下雨之后能接...
  • 最近在看算法,看到了动态规划那里,都说这个很难的,但是我硬着头皮看了下来,然后觉得又是可以接受的。我觉得有时候先看算法思想的描述和一些概念性的术语总是会看得糊里糊涂的,先不要深琢算法的思想,也可以看...
  • 前言 做产品的初期踩过不少坑,流程图的坑就是其中一个。...五层思考产品启动到落地中的流程图的地位 实际工作场景中流程图的意义 业务流程图、功能流程图、页面流程图的使用场景和作用 归纳总结 五
  • 实验二:矩阵连乘(动态规划

    千次阅读 2020-06-05 12:14:27
    1.掌握动态规划算法的基本思想、技巧和效率分析方法。  2.熟练掌握动态规划算法的最优子结构性质的分析与证明。  3.学会利用动态规划算法解决实际问题。 3.实验要求 (1)根据实验内容构思设计算法,选取适合的数据...
  • 首先简略介绍一下旅行商问题:有n个...今天给大家介绍一种动态规划解法,本文的程序编写是受到这位大神的文章启发,有兴趣的同学也可以去看看。 回到旅行商的一个具体问题,假如有城市、、、,要从开始访问所有城...
  • 动态规划之矩阵连乘

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 31,601
精华内容 12,640
关键字:

动态规划法流程图

友情链接: img_red.gz