精华内容
下载资源
问答
  • 一个简单的动态规划算法实例,实现硬币找零的最小硬币数以及每种面额硬币的数量。
  • 矩阵连乘动态规划C语言实现。简单的操作,使得大家更容易理解动态规划的思想,测试可用。
  • 动态规划C语言矩阵连乘Acm acm 采用动态规划来解题
  • 租用游艇问题 动态规划 C语言

    千次阅读 2019-12-25 15:55:16
    简单的动态规划方法实现游艇问题 #include <stdio.h> #include <stdlib.h> int r[10][10]; int payment(int n) { for(int i=n; i>=1; i--) { for(int j=i; j<=n; j++) { if ...

    简单的动态规划方法实现游艇问题

    #include <stdio.h>
    #include <stdlib.h>
    int r[10][10];
    int payment(int n)
    {
        for(int i=n; i>=1; i--)
        {
            for(int j=i; j<=n; j++)
            {
                if (i==j)r[i][j]=0;
                else
                {
                    for(int t=i+1; t<j; t++)
                    {
                        int tmp;
                        tmp=r[i][t]+r[t][j];
                        if (tmp<=r[i][j])
                        {
                            r[i][j]=tmp;
                        }
                    }
                }
            }
        }
        return r[1][n];
    }
    int main()
    {
        int n;
        scanf("%d",&n);
        for(int i=1; i<n; i++)
        {
            for(int j=i+1; j<=n; j++)
            {
                scanf("%d",&r[i][j]);
            }
        }
        int sum=payment(n);
        printf("租金为 %d 元",sum);
        return 0;
    }
    
    
    
    展开全文
  • 动态规划法 题目描述:给定n个矩阵{A1,A2….An},其中Ai与Ai+1是可以相乘的,判断这n个矩阵通过加括号的方式相乘,使得相乘的次数最少! 以矩阵链ABCD为例 按照矩阵链长度递增计算最优值 矩阵链长度为1时,分别...
  • 因此,可以使用数字保存中间的计算结果,和动态规划类似。这道题应该当作动态规划的练习题。dp方程为dp[n] = dp[n-1] + dp[n-2],一目了然。 //典型的斐波那契数列数列,采用dp方法。 //dp[n] = dp[n-2] + dp[n...
    假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
    每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢?
    注意:给定 n 是一个正整数。
    
    示例 1:
    输入: 2
    输出: 2
    解释: 有两种方法可以爬到楼顶。
    1.  1 阶 + 1 阶
    2.  2 阶
    
    示例 2:
    输入: 3
    输出: 3
    解释: 有三种方法可以爬到楼顶。
    1.  1 阶 + 1 阶 + 1 阶
    2.  1 阶 + 2 阶
    3.  2 阶 + 1 阶

    这道题写一个例子就能发现和斐波那契数列数列极为相似。算法课上介绍递归的时候就出现过,使用递归解决斐波那契数列问题。不过,虽然递归可解。f(n) = f(n-1)+f(n-2),但是存在大量重复计算,计算f3的时候需要计算f2和f1,计算f4的时候,需要计算f3和f2。这样算下去,存在大量重复计算开销。因此,可以使用数字保存中间的计算结果,和动态规划类似。这道题应该当作动态规划的练习题。dp方程为dp[n] = dp[n-1] + dp[n-2],一目了然。

    //典型的斐波那契数列数列,采用dp方法。
    //dp[n] = dp[n-2] + dp[n-1];
    
    int climbStairs(int n){
        int *dp, i;
        
        //特殊情况处理
        if (n < 2)
            return 1;
        
        dp = (int *)calloc(n+1, sizeof(int));
        
        //边界条件初始化
        dp[0] = 0;
        dp[1] = 1;
        dp[2] = 2;
        
        for (i = 3; i <= n; i++)
            dp[i] = dp[i-2] + dp[i-1];
        return dp[n];
    }

    =============================================================================================

    Linux应用程序、内核、驱动开发交流讨论群(745510310),感兴趣的同学可以加群讨论、交流、资料查找等,前进的道路上,你不是一个人奥^_^。

    展开全文
  • 课程的随堂作业,C语言的,用dev就能运行,萌新代码,勿喷,仅仅帮助不想写作业的朋友方便一下,反正老师也不会仔细检查的
  • 动态规划C语言初学

    万次阅读 多人点赞 2017-04-04 15:54:44
    动态规划问题解决的基本思想: 1、根绝问题所求的那一项和变量的个数,确定是一维数组,二维数组或者多维数组。 2、写出初始值,一般是某个变量为1或者0 的特殊情况时候的解。 3、通过循环,一般是两个循环中间每一...
     
    


    动态规划问题解决的基本思想:

    1、根绝问题所求的那一项和变量的个数,确定是一维数组,二维数组或者多维数组。

    2、写出初始值,一般是某个变量为1或者0 的特殊情况时候的解。

    3、通过循环,一般是两个循环中间每一层循环表示一个变量的递增情况。

    4、在循环中间写出对应的递推关系表达式,求出问题的每一项。

    5、根据题意得到答案,一般是数组的最后一项。

    提示 : 找递推关系是动态规划最难的一步,所以不要懒敲打,一定要在草稿纸上去画出来二维表的情况,一般只要看看自己画的表就可以得到规律。

     

    一、走方格问题

    1.问题引入:

    有一个矩阵map,它每个格子有一个权值。从左上角的格子开始每次只能向右或者向下走,最后到达右下角的位置,路径上所有的数字累加起来就是路径和,返回所有的路径中最小的路径和。给定一个矩阵map及它的行数n和列数m,请返回最小路径和。保证行列数均小于等于100.
    输入输出样例:

    第一行,输入n,m表示这个矩阵的行数和列数,接下来的n行,输入每行的m个数字,也即每个格子的权值。最后输出最小路径和。如:

    2 3

    1 2 3

    1 1 1

    输出:4

    2.思路分析 :

    因为只能向右和向下,所以从第一个格子到某个格子(不在第一排也不在第一列,否则没有编程的必要了)的最短距离只与第一个格子到它左边格子的最短距离以及第一个格子到它上面格子的最短距离这两个值有关,取这两个值中的较小者。可以设dp[n][m]为走到n*m位置的最短路径长度,则dp[n][m] = Min(dp[n-1][m],dp[n][m-1]),这就运用到了动态规划的思想。题目要求算出复杂情况的值,而动态规划则是算出几个简单的作为已知值,然后找规律由后往前推理。

    3.代码如下:

    #include<stdio.h>
    #include<stdlib.h>
    int a[100][100];
    int dp[100][100]; 
    
    int Min(int a,int b){
    	if(a<b){
    		return a;
    	}else{
    		return b;
    	}
    }
    
    int getMin(int m,int n){
    	int min;
    	
    	dp[0][0]=a[0][0];
    	for(int i=1;i<m;i++){
    		dp[i][0]=a[i][0]+dp[i-1][0];
    	}
    	for(int i=1;i<n;i++){
    		dp[0][i]=a[0][i]+dp[0][i-1];
    	}
    	
    	for(int i=1;i<m;i++){
    		for(int j=1;j<n;j++){
    			min=Min(dp[i-1][j],dp[i][j-1]);
    			dp[i][j]=min+a[i][j];
    		}
    	}
    	
    	return dp[m-1][n-1];
    }
    
    int main(){
    	int m,n;
    	scanf("%d%d",&m,&n);
    	
    	for(int i=0;i<m;i++){
    		for(int j=0;j<n;j++){
    			scanf("%d",&a[i][j]);
    		}
    	}
    		
    	printf("%d\n",getMin(m,n));
    
    	return 0;
    } 

     

     

    二、最长公共序列数问题

    1.问题引入:

    给定两个字符串A和B,返回两个字符串的最长公共子序列的长度。例如,A="1A2C3D4B56”,B="B1D23CA45B6A”,”123456"或者"12C4B6"都是最长公共子序列。给定两个字符串A和B,同时给定两个串的长度n和m,请返回最长公共子序列的长度。保证两串长度均小于等于300。测试样例:第一行输入一个字符串,第二行输入这个字符串的长度,第三行和第四行也分别输入一个字符串和这个字符串的长度。最后输出结果。如:1A2C3D4B56

    10

    B1D23CA45B6A

    12返回:6

    2.思路分析:

    设dp[n][m] ,为A的前n个字符与B的前m个字符的公共序列长度,则当A[n]==B[m]的时候,dp[i][j] =
    max(dp[i-1][j-1]+1,dp[i-1][j],dp[i][j-1]),否则,dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1]);

     3.代码如下:

    #include<stdio.h>
    #include<string.h>
    int dp[100][100];
    
    int Max(int a,int b,int c){
    	int max=a;
    	if(b>max){
    		max=b;
    	}
    	if(c>max){
    		max=c;
    	}
    	return max;
    }
    
    int getMax(char s1[],char s2[],int m,int n){
    	int i,j;
    	
    	for(i=0;i<m;i++){       //当 s2取 1个的时候 ,s1为可变长度 
    		if(s1[i]==s2[0]){
    			dp[i][0]=1;
    			for(j=i+1;j<m;j++){
    				dp[j][0]=1;
    			}
    			break;
    		} 
    	}
    	for(i=0;i<n;i++){      //当 s1取 1个的时候 ,s2为可变长度 
    		if(s2[i]==s1[0]){
    			dp[0][i]=1;
    			for(j=i+1;j<n;j++){
    				dp[0][j]=1;
    			}
    			break;
    		} 
    	} 
    	
    	for(i=1;i<m;i++){
    		for(j=1;j<n;j++){
    			if(s1[i]==s2[j]){
    				dp[i][j]=Max(dp[i-1][j-1]+1,dp[i-1][j],dp[i][j-1]);
    			}else{
    				dp[i][j]=dp[i-1][j]>=dp[i][j-1]?dp[i-1][j]:dp[i][j-1];
    			}
    		}
    	} 
    	return dp[m-1][n-1];
    }
    
    int main(){
    	int m,n;
    	char s1[100];
    	char s2[100];
    	gets(s1);
    	gets(s2);
    	m=strlen(s1);
    	n=strlen(s2);
    	
    	printf("%d\n",getMax(s1,s2,m,n));
    
    	return 0;
    }

     

     

    三、密码脱落

    1.问题引入:

    X星球的考古学家发现了一批古代留下来的密码。

    这些密码是由A、B、C、D 四种植物的种子串成的序列。

    仔细分析发现,这些密码串当初应该是前后对称的(也就是我们说的镜像串)。

    由于年代久远,其中许多种子脱落了,因而可能会失去镜像的特征。

     

    你的任务是:

    给定一个现在看到的密码串,计算一下从当初的状态,它要至少脱落多少个种子,才可能会变成现在的样子。

     

    输入一行,表示现在看到的密码串(长度不大于1000)

    要求输出一个正整数,表示至少脱落了多少个种子。

    例如,输入:

    ABCBA

    则程序应该输出:

    0

    再例如,输入:

    ABDCDCBABC

    则程序应该输出:

    3

    2.思路分析:

    这道题一定要明白回文构成的颠倒现象,可以用两个字符串去实现,一个是原字符串,另一个则是源字符串反过来的字符串,只要匹配两者的最大的相同序列,用长度减去即可求得答案。

    3.代码如下:

    #include<stdio.h>
    #include<string.h>
    int dp[100][100];
    
    int Max(int a,int b,int c){
    	int max=a;
    	if(b>max){
    		max=b;
    	}
    	if(c>max){
    		max=c;
    	}
    	return max;
    }
    
    int getMax(char s1[],char s2[],int m){
    	int i,j;
    	for(i=0;i<m;i++){
    		if(s1[0]==s2[i]){
    			dp[0][i]=1;
    			for(j=i+1;j<m;j++){
    				dp[0][j]=1;
    			}
    			break;
    		}
    	}
    	for(int i=0;i<m;i++){
    		if(s1[i]==s2[0]){
    			dp[i][0]=1;
    			for(j=i+1;j<m;j++){
    				dp[j][0]=1;
    			}
    			break;
    		}
    	}
    	
    	for(i=1;i<m;i++){
    		for(j=1;j<m;j++){
    			if(s1[i]==s2[j]){
    				dp[i][j]=Max(dp[i-1][j-1]+1,dp[i-1][j],dp[i][j-1]);
    			}else{
    				dp[i][j]=dp[i-1][j]>=dp[i][j-1]?dp[i-1][j]:dp[i][j-1];
    			}
    		}
    	}
    	
    	return m-dp[m-1][m-1];
    }
    
    int main(){
    	int m,n;
    	char s1[100];
    	char s2[100];
    	gets(s1);
    	m=strlen(s1);
    	for(n=0;n<m;n++){
    		s2[n]=s1[m-n-1];
    	}
    
    	printf("%d\n",getMax(s1,s2,m));
    	
    	return 0;
    }

     

     

    四、硬币凑数问题

    1.问题引入:

    假设现在有面值为1元、3元和5元的硬币若干枚,如何用最少的硬币凑够需要的钱数。现输入一个数,表示需要的钱数,要求输出一个整数表示最小的硬币数。

    2.思路分析:

    动态规划算法广泛地用于最优化问题中,在我们从 1 元开始依次找零时,可以尝试一下当前要找零的面值(这里指 1 元)是否能够被分解成另一个已求解的面值的找零需要的硬币个数再加上这一堆硬币中的某个面值之和,如果这样分解之后最终的硬币数是最少的,那么问题就得到答案了。这就是动态规划的思想。

    3.代码如下:

    #include<stdio.h>
    int min[10000];
    int kinds[]={5,2,1};
    
    int f(int n,int m){
    	min[0]=0; 
    	min[1]=1;           
    	for(int i=2;i<m+1;i++){
    		int a=m;
    		for(int j=0;j<n;j++){
    			if(kinds[j]<=i){
    				int t=min[i-kinds[j]]+1;
    				a=a<t?a:t;
    			}
    		}
    		min[i]=a;
    	}
    	return min[m];
    }
    
    int main(){
    	
    	int m;
    	scanf("%d",&m);
    	printf("%d\n",f(3,m)); 
    	return 0;
    }

     

     

    五、K好数

    1.问题描述

    如果一个自然数N的K进制表示中任意的相邻的两位都不是相邻的数字,那么我们就说这个数是K好数。求L位K进制数中K好数的数目。例如K = 4,L = 2的时候,所有K好数为11、13、20、22、30、31、33 共7个。由于这个数目很大,请你输出它对1000000007取模后的值。

    输入格式

    输入包含两个正整数,K和L。

    输出格式
    输出一个整数,表示答案对1000000007取模后的值。
    样例输入
    4 2
    样例输出
    7
    数据规模与约定

    对于30%的数据,KL <= 106

    对于50%的数据,K <= 16, L <= 10;

    对于100%的数据,1 <= K,L <= 100。

    2.思路:

    第i位数放置j所得到的所有K好数由i-1进制数的所有K好数之和去除与j相邻的两种情况求得。

    3.代码如下:
    #include<stdio.h>
    int dp[100][100];
    int getAns(int k,int l){
    	int i,j,t,sum=0;
    	for(i=0;i<k;i++){
    		dp[1][i]=1;
    	}
    	for(i=2;i<=l;i++){
    		for(j=0;j<k;j++){
    			for(t=0;t<k;t++){
    				if(t!=j-1&&t!=j+1){
    					dp[i][j]+=dp[i-1][t];
    				}
    			}
    		}
    		dp[i][j]%=100000008;
    	}
    	for(j=1;j<k;j++){
    		sum=sum+dp[l][j];
    		sum%=100000008;
    	}
    	return sum;
    }
    int main(){
    	int k,l;
    	scanf("%d%d",&k,&l);
    	printf("%d\n",getAns(k,l));
    	return 0;
    }

    六、01背包问题

    1.问题引入:

    有编号分别为a,b,c,d,e的五件物品,它们的重量分别是2,2,6,5,4,它们的价值分别是6,3,5,4,6,现在给你个承重为10的背包,如何让背包里装入的物品具有最大的价值总和?
    2.思路分析:
    nameweightvalue12345678910
    a26066991212151515
    b23033669991011
    c65000666661011
    d54000666661010
    e460006666666

     

    过找规律手工填写出上面这张表就能理解背包的动态规划算法了。状态转移方程为:

    f[i,j] = Max{ f[i-1,j-Wi]+Pi( j >= Wi ),//表示第i件物品放入

     f[i-1,j] //表示第i件物品不放入}

    首先要明确这张表是至底向上,从左到右生成的。
    为了叙述方便,用e2单元格表示e行2列的单元格,这个单元格的意义是用来表示只有物品e时,有个承重为2的背包,那么这个背包的最大价值是0,因为e物品的重量是4,背包装不了。
    对于d2单元格,表示只有物品e,d时,承重为2的背包,所能装入的最大价值,仍然是0,因为物品e,d都不是这个背包能装的。
    同理,c2=0,b2=3,a2=6。
    对于承重为8的背包,a8=15,是怎么得出的呢?
    在这里,
    f[i-1,j]表示我有一个承重为8的背包,当只有物品b,c,d,e四件可选时,这个背包能装入的最大价值
    f[i-1,j-Wi]表示我有一个承重为6的背包(等于当前背包承重减去物品a的重量),当只有物品b,c,d,e四件可选时,这个背包能装入的最大价值
    f[i-1,j-Wi]就是指单元格b6,值为9,Pi指的是a物品的价值,即6
    由于f[i-1,j-Wi]+Pi = 9 + 6 = 15 大于f[i-1,j] = 9,所以物品a应该放入承重为8的背包
    3.代码如下:
    #include<stdio.h>
    int v[]={6,3,5,4,6};
    int w[]={2,2,6,5,4};
    int dp[100][100];
    
    int Max(int a,int b){
    	if(a>=b){
    		return a;
    	}else{
    		return b;
    	}
    }
    
    int getAns(int i,int wi){
    	
    	for(int x=0;x<=i;x++){
    		dp[x][0]=0;
    	}
    	for(int x=0;x<=wi;x++){
    		dp[0][x]=0;
    	}
    	
    	for(int x=1;x<=i;x++){
    		for(int y=1;y<=wi;y++){
    			if(y>=w[x-1]){
    				dp[x][y]=Max(dp[x-1][y],v[x-1]+dp[x-1][y-w[x-1]]);
    			}else{
    				dp[x][y]=dp[x-1][y];
    			}
    			printf("%4d",dp[x][y]);
    		}
    		printf("\n");
    	}
    	return dp[i][wi];
    }
    
    
    int main(){
    	int max=getAns(5,10);
    	printf("%d\n",max);
    	return 0;
    } 
    

     

     

    七、有向五环图最短路径问题

    1.问题引入:



     

    2.思路分析:



    3.代码如下:

    #include<stdio.h>
    #define x 9999;
    #define max 9999;
    int dist[10];
    	
    void f(int a[][11]){
    		int i,j,k;
    		dist[0]=0;
    		for(i=1;i<10;i++){
    			k=max;
    			for(j=0;j<i;j++){
    				if(a[j][i]!=0){
    					if(dist[j]+a[j][i]<k){
    						k=dist[j]+a[j][i];
    					}
    					dist[i]=k;
    				
    				}
    			}
    		}
    }
    
    int main(){
    	int i;
    	int a[][11] = { { 0, 4, 2, 3, 0, 0, 0, 0, 0, 0 },
    				{ 0, 0, 0, 0, 10, 9, 0, 0, 0, 0 },
    				{ 0, 0, 0, 0, 6, 7, 10, 0, 0, 0 },
    				{ 0, 0, 0, 0, 0, 3, 8, 0, 0, 0 },
    				{ 0, 0, 0, 0, 0, 0, 0, 4, 8, 0 },
    				{ 0, 0, 0, 0, 0, 0, 0, 9, 6, 0 },
    				{ 0, 0, 0, 0, 0, 0, 0, 5, 4, 0 },
    				{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 8 },
    				{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 4 },
    				{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 } };
    	f(a);
    	printf("%d\n",dist[9]);
    } 
     
     
    最后:动态规划的思想可以解决很多算法中的问题,以上的几个题型只供大家初学的时候学习,如果有哪里写的有问题还希望大家指正,大家一起学习。大笑
     
    展开全文
  • 动态规划C语言.ppt

    2020-08-22 04:02:01
    输出一个盘子的移动方案 procedure _move(number , st , ed : longint;{ 将盘子 number 从 st 柱移至 ed 柱 } begin write'move ' , number , ' from ' , st , ' to ' , ed; if stack[ed].tot > 0 then write' atop ...
  • 子序列:给定一个序列X=<x1,x2,x3,x4...,xm>,另一个序列Z=<z1,z2,z3,z4...,zk>,若存在一个严格递增的X的下标序列<i1,i2,i3,...,ik>对所有的1,2,3,...,k,都满足x(ik)=zk,则称Z是X的子序列(不...

    子序列:给定一个序列X=<x1,x2,x3,x4...,xm>,另一个序列Z=<z1,z2,z3,z4...,zk>,若存在一个严格递增的X的下标序列<i1,i2,i3,...,ik>对所有的1,2,3,...,k,都满足x(ik)=zk,则称Z是X的子序列(不一定要连续但顺序必须相同)

    补充:字符子串和字符子序列的区别

    字符字串指的是字符串中连续的n个字符;如palindrome中,pa,alind,drome等都属于它的字串

    而字符子序列指的是字符串中不一定连续但先后顺序一致的n个字符;如palindrome中,plind,lime属于它的子序列,而mod,rope则不是,因为它们与字符串的字符顺序不一致。

    那么如何由dp求出LCS呢?

    (1)当元素值等于上方相邻元素值时i-1,即dp[i][j]=dp[i-1][j]

    (2)当元素值等于左方相邻元素值时j-1,即dp[i][j]=dp[i][j-1]

    (3)若元素值与上方、左方元素均不相等时,说明字符相同了,将a[i]添加到数组中

    LCS算法由于使用了两重循环,所以对于长度分别为m、n的序列,其时间复杂度和空间复杂度都是O(mn)

    图解如下: 

    完整代码如下:

    #include <stdio.h> 
    #include <string.h>
    using namespace std;
    const int MAXSIZE=1001;
    char a[MAXSIZE];
    char b[MAXSIZE];
    int c[MAXSIZE][MAXSIZE];
    char dp[MAXSIZE][MAXSIZE];
    
    void LCS(int m,int n){
        //先初始化
    	for(int i=0;i<=m;i++) c[i][0]=0;
    	for(int j=0;j<=n;j++) c[0][j]=0;
        //两重循环处理a、b的所有字符 
    	for(int i=1;i<=m;i++){
    		for(int j=1;j<=n;j++){
    			if(a[i]==b[j]){
    				c[i][j]=c[i-1][j-1]+1;
    				dp[i][j]='W';        //此时有相同的字符 
    			}else if(c[i-1][j]>=c[i][j-1]){
    					c[i][j]=c[i-1][j];  
    					dp[i][j]='U';    //此时没有相同的字符
    	     	}else{
    	     	    c[i][j]=c[i][j-1];
    				dp[i][j]='L';        //此时也没有相同的字符 
    				}
    			}
    		}
    }
    
    void Print(int m,int n){
    	int i=m;
    	int j=n;
    	if(i==0||j==0) return;
    	if(dp[i][j]=='W'){
    		Print(i-1,j-1);    //相同,沿对角线走,且需要输出 
    		printf("%c",a[i]);
    	}else if(dp[i][j]=='U'){ 
    		Print(i-1,j);      //向上走 
    	}else Print(i,j-1);    //向左走
    }
    
    int main(){
    	scanf("%s %s",a+1,b+1); 
    	int m=strlen(a+1);
    	int n=strlen(b+1);
    	LCS(m,n);
    	Print(m,n);
    }

    展开全文
  • 动态规划C语言实现之最长公共子序列(LCS)

    万次阅读 多人点赞 2018-02-06 23:09:28
    我的机器学习教程「美团」算法工程师带你入门机器学习 已经开始更新了,欢迎大家订阅~ 任何关于算法、编程、AI行业知识或博客内容的问题,可以随时扫码关注公众号「图灵的猫」,加入”学习小组“,沙雕博...动态规...
  • 最长递增公共子序列、最长公共子串、最小编辑代价等经典动态规划问题的详细代码
  • c语言实现了动态规划算法,输入为路径的一个邻接矩阵
  • 给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额,返回 -1。 示例 1: 输入: coins = [1, 2, 5], amount = 11 输出: 3...
  • 01背包问题 动态规划 c语言实现

    千次阅读 2017-09-06 16:15:47
    *这是DP的一个经典实例,可以用动态规划求解 *设dp(i,j)表示对于前i件物品,背包剩余容量为j时,能取得的最大价值 *状态转移方程:dp(i,j) = Max(dp(i-1,j), dp(i-1,j-w[i])+v[i]) *注: dp(i-1,j) -----》 dp(i...
  • 课程的随堂作业,C语言的,用dev就能运行,萌新代码,勿喷,仅仅帮助不想写作业的朋友方便一下,反正老师也不会仔细检查的
  • 不为0时表明子问题已求解,直接返回结果,这种方法也叫备忘录方法,是动态规划的一种变形。 完整代码如下: #include #include #define MAXN 500 int dp[MAXN][MAXN]; int dpn(int n,int k){ if(dp[n][k]!=0) ...
  • //动态规划类型,考虑每一个最大值都可以有哪些子问题构成 //例如:我要从前四个里面偷取,怎么偷呢! //细思极恐,好几种可能。怎么办呢?记住,编程时就是将乱麻给捋顺 //这些可能可以分为以下几大类:肯定...
  • 基本动态规划法的核反应堆问题的C程序,按课程设计的标准写的,使用基本数据类型,没有考虑大数相加问题
  • 各种背包问题动态规划(C语言实现)

    千次阅读 2020-05-13 11:38:40
    算法核心: 首先,需要设置一个二维数组t[][],其中t[i][j]表示利用前i个物品来装进容量为j的背包的所能够获得的最大价值。 当只考虑第i件物品时,可将情况分为是否放入第i件物品两种: 1.01背包——每个物品仅有一...
  • 题目描述 有n个物品,它们有各自的体积和价值,现有给定容量的背包,如何让背包里装入的物品具有最大的价值总和? 举一个例子: 有一个小偷他有一个容量为8的背包 物体的体积和价值如下所示: ...用动态规划的方法来解决
  • 课程的随堂作业,C语言的,用dev就能运行,萌新代码,勿喷,仅仅帮助不想写作业的朋友方便一下,反正老师也不会仔细检查的
  • c语言实现的基于动态规划求解01背包问题,,其中2.txt中的内容为: 4 5 2 1 3 2 12 10 20 15
  • 今天又上了一节算法设计与分析课,头疼,学了动态规划的思想解决最值问题,行了,不啰嗦了,直接上干货干吧!!! 二.内容 题目: 三.分析过程 符合动态规划问题最值问题,故用动态规划来求解。 1.确定状态 本题...
  • 背包问题C语言实现, 如要不同格式的输出,修改main函数即可
  • 数字三角形之动态规划(C语言实现)

    千次阅读 2020-05-17 16:49:39
    算法步骤: (1)首先构造三个数组,第一个是存储三角形初始值的数组data[][];第二个是存储顶点到该点最大值的res[][]数组;第三个是存储该点上一个点的loc[][]数组。这里要对res[][]数组进行初始化-1;...
  • 常用算法案例之动态规划C语言

    千次阅读 2019-04-30 10:56:30
    // 动态规划之最长公共子序列.cpp : 定义控制台应用程序的入口点。 // #include "stdafx.h" /***最长公共子序列***/ /*动态规划*/ #include<stdio.h> #include<string.h> #include<stdlib.h> #...
  • 最长递增子序列之动态规划(C语言实现)

    千次阅读 多人点赞 2020-05-10 23:30:00
    } //初始化mark[]数组,采用动态规划 void MaxLongSequence(){ int i,j,max; mark[0]=1; loc[0]=-1; for(i=0;i;i++) //表示以i为结尾的序列 { max=0; //及时初始为0 for(j=0;j;j++) if(data[i]>data[j]...
  • 然后用C语言实现这个具体问题。 #include<stdio.h>//求最长公共子序列的长度 //#include<string.h> int main(){ int max(int a,int b); int i;//循环变量 int j;//循环变量 int a[7][8]; char s2[7...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 20,862
精华内容 8,344
关键字:

动态规划c语言

c语言 订阅