精华内容
下载资源
问答
  • /*在编号为a,b,c,d,e 的五件物品,他们的重量分别是2,2,6,5,4.价值分别是6,3,5,4,6,给你...* 背包最多承重为W,在不超出承重范围的前提下,求能拿的物件的最大价值为多少**这是DP的一个经典实例,可以用动态规划求...

    /*

    在编号为a,b,c,d,e 的五件物品,他们的重量分别是2,2,6,5,4.价值分别是6,3,5,4,6,给你个承重是10的背包,如何让装入背包的物品具有最大价值.

    *//*

    * 基本的0-1背包问题:

    * 已知有N类物品,每类物品都只有一件,对应的重量为w[i],价值为v[i]。

    * 背包最多承重为W,在不超出承重范围的前提下,求能拿的物件的最大价值为多少

    *

    *这是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,j),即不拿第i件物品

    * dp(i-1,j-w[i]) -----》 dp(i,j),即拿第i件物品

    * 当物品数量很多,背包的容量很大时,这时要用二维数组往往是不现实的

    * 我们可以进行空间压缩,使用一维数组实现

    * 状态转移方程:

    * dp(j)=Max(dp(j),dp(j-w[i])+v[i])

    * 注:对于背包的容量要采用倒序的方式!

    */

    #include

    #include

    using namespace std;

    #define N 5 // N件宝贝

    #define V 10 // C是背包的总capacity

    int main()

    {

    int value[N + 1] = {0, 6, 3, 5, 4, 6}; // 钱

    int weight[N + 1] = {0, 2, 2, 6, 5, 4}; // 重量

    int f[N + 1][V + 1] = {0}; // f[i][j]表示在背包容量为j的情况下, 前i件宝贝的最大价值

    int i = 1;

    int j = 1;

    for(i = 1; i <= N; i++)

    {

    for(j = 1; j <= V; j++)

    {

    // 递推关系式

    if(j < weight[i])

    {

    f[i][j] = f[i - 1][j];

    }

    else

    {

    //决策:在背包承重是j的情况下,有第i件物品和没有第i件物品哪个总的价值更加大.

    int x = f[i - 1][j];

    int y = f[i - 1][j - weight[i]] + value[i];

    f[i][j] = x < y ? y : x;

    }

    }

    }

    for(i = N; i >= 1; i--)

    {

    for(j = 1; j <= V; j++)

    {

    printf("%4d ", f[i][j]);

    }

    cout << endl;

    }

    return 0;

    }

    展开全文
  • 两个字符相等时,只需要copy左上角的元素 最后得到 #include #include //取a和b、c中最小的值 int min(int a, int b, int c) { int temp = a ; return temp < c ? temp : c; } int myCharDistance(char str1[], char...

    【问题描述】设A和B是两个字符串,要用最少的字符操作将字符串A转换为字符串B。这里所说的字符操作包括:

    (1)删除一个字符;
    (2)插入一个字符;
    (3)将一个字符改为另一个字符。
    将字符串A变换为字符串B所用的最少字符操作数称为字符串A到B的编辑距离,记为d(A,B)。试设计一个有效算法,对任给的两个字符串A和B,计算出它们的编辑距离dp(A,B)。

    图解如下:

    第1行:

    空字符串需要经过多少次变换才可以变成另一个空字符串,显然是0,所以第一空是0

    空字符串需要经过多少次变换才可以变成字符串a, 显然是1次,即操作(2)

    空字符串需要经过多少次变换才可以变成字符串ap, 显然是2次,即操作(2)

    空字符串需要经过多少次变换才可以变成字符串app, 显然是3次,即操作(2)

    以此类推得到如下表

     第1列:

    字符o需要经过多少次变换才可以变成空字符串,显然是1次,即操作(1)

    字符op需要经过多少次变换才可以变成空字符串,显然是2次删除,即操作(1)

    以此类推得到如下表

     

    第2列:

    字符o需要经过多少次变换才可以变成字符串a,因为两个字符不等,所以从相邻的三个元素中找最小值+1,其中,这个元素的左上角元素代表的含义是:经过多少次变换后已经变成它上面正对着的字符(操作3)

     两个字符相等时,只需要copy左上角的元素

    最后得到

     

    #include<stdio.h>
    #include<string.h>
    
    //取a和b、c中最小的值 
    int min(int a, int b, int c)
    {
    	int temp = a < b ? a : b; 
    	return temp < c ? temp : c;
    }
    
    int myCharDistance(char str1[], char str2[])
    {
    	int i, j, len1, len2;
    	int dist[100][100];
    	len1 = strlen(str1);
    	len2 = strlen(str2);
    
    	for(i = 0; i <= len1; i++)
    		dist[i][0] = i;
    	for(j = 0; j <= len2; j++)
    		dist[0][j] = j;
    
    	for(i = 1; i <= len1; i++)
    		for(j = 1; j <= len2; j++) {
    //因为dist比str1和str2多了第0行和第0列,str是从下标0开始存数,而dist[]是从下标1才开始真正存数,
    //所以dist[i]对应str[i - 1], 里一定要注意。
    			if(str1[i - 1] == str2[j - 1])   
    				dist[i][j] = dist[i - 1][j - 1];
    			else {
    				int insert = dist[i][j - 1] + 1;  //插入操作 
    				int dele = dist[i - 1][j] + 1;    //删除操作 
    				int replace = dist[i - 1][j - 1] + 1;   //替换操作 
    				dist[i][j] = min(insert, dele, replace);
    			}
    		}
    
    	return dist[len1][len2];
    }
    
    int main()
    {
    	char str1[100], str2[100];
    
    	gets(str1);
    	gets(str2);
    
    	printf("min distance between this two char is:%d\n", myCharDistance(str1, str2));
    
    	return 0;
    }
    

    展开全文
  • 今天又上了一节算法设计与分析课,头疼,学了动态规划的思想解决最值问题,行了,不啰嗦了,直接上干货干吧!!! 二.内容 题目: 三.分析过程 符合动态规划问题最值问题,故用动态规划来求解。 1.确定状态 本题...

    一.前言

    今天又上了一节算法设计与分析课,头疼,学了动态规划的思想解决最值问题,行了,不啰嗦了,直接上干货干吧!!!

    二.内容

    题目:
    在这里插入图片描述

    三.分析过程

    符合动态规划问题最值问题,故用动态规划来求解。

    在这里插入图片描述
    1.确定状态
    在这里插入图片描述
    本题中用一维数组就行,a[i]代表解决问题所用的最少硬币数(a[i]详见后续代码)
    当最后一步硬币面额可以取2,5,7时。前几枚硬币(k-1枚硬币)的币数为f(25),f(22),f(20).总次数就为f(25)+1,f(22)+1,f(20)+1中最小的值了。(f(25),f(22),f(20)只是变量,目前次数不确定)
    在这里插入图片描述
    2.转移方程(就是将上面的思路一般化)
    在这里插入图片描述
    3.确定初始条件和边界情况
    在这里插入图片描述
    f(0)=0很好理解,买一本需要0元,还需要付硬币吗?自然是硬币数自然是0,f(负数)=无穷大,也好理解,当买一本书需要负元时,这种情况当然不存在,(你买一本书,别人还倒贴你钱,孩子你想多,这种美事当然不存在),所以这种情况不可以取,又是用求三个的最小值,所以用正无穷表示。
    4.计算顺序
    (我们倒推,当然正着来求解啊,一般来说,动态规划问题都是O(n),用数组保留原问题的解)
    在这里插入图片描述
    四.效果图(本例用10000表示无穷大)
    在这里插入图片描述
    五.代码(这是我喜欢的一部分,不知道怎么了,今天居然废话了一堆,噼里啪啦讲了一堆,行了,不继续废话了,直接肝)

    #include<stdio.h>
    #define M 10000 //M表示无穷
    #define Max 1000 
    int main(){
    	int min(int a,int b,int c);
    	int a[Max];//用来存储次数
    	int count=0;//计数换行 
    	int f_i2,f_i5,f_i7;
    	int i;//循环变量
    	a[0]=0;
    	for(i=1;i<=27;i++){
    		if((i-2)<0){
    			f_i2=M;
    		}
    		else{
    			f_i2=a[i-2];
    		} 
    		
    		if((i-5)<0){
    			f_i5=M;
    		}
    		else{
    			f_i5=a[i-5];
    		} 
    
    		if((i-7)<0){
    			f_i7=M;
    		}
    		else{
    			f_i7=a[i-7];
    		} 
    		
    		a[i]=min(f_i2+1,f_i5+1,f_i7+1);
    	}
    	for(i=0;i<28;i++){
    		printf("%d ",a[i]);
    		count++;
    		if(count%5==0){
    			printf("\n");
    		}
    	}
    	return 0;
    }
    
    int min(int a,int b,int c){//求三个数的最小值
    	int min_n;
    	min_n=a<b?a:b;
    	return min_n<c?min_n:c;
    }
    
    展开全文
  • 动态规划C语言综述动态规划 思路 先看第5阶段,到达A点有两条路 B ? A,需要2km C ? A,需要3km 令 从P ? A的最短路径为P(A); 从P ? B的最短路径为P(B); 从P ? C的最短路径为P(C) …… P(A) = min{P(B)+2, P(C)+3}...

    动态规划C语言综述

    动态规划 思路 先看第5阶段,到达A点有两条路 B ? A,需要2km C ? A,需要3km 令 从P ? A的最短路径为P(A); 从P ? B的最短路径为P(B); 从P ? C的最短路径为P(C) …… P(A) = min{P(B)+2, P(C)+3}; P(B) = min{P(D)+1, P(E)+2}; P(C) = min{P(E)+5, P(F)+4}; P(A) = min{P(B)+2, P(C)+3}; P(B) = min{P(D)+1, P(E)+2}; P(C) = min{P(E)+5, P(F)+4}; D 1 B 2 A 2 3 5 P(B) E C 4 P(C) F P(N) = 2; P(O) = 3; 选择数据结构,将每条路经的长度存在数组中。 东西方向上的道路长度存在两维数组h[4][3]中规定数组的第一维为行号,第二维为列号。 南北方向上道路长度存至数组v[3][4]中,也规定第一维为行号,第二维为列号。 为了计算方便,将图1改为图2 求解过程为从(0, 0)到(3, 3)求最短路径问题 定义二维数组,P[4][4]={{0,0,0,0},{0,0,0,0},{0,0,0,0},{0,0,0,0}},第一维为行,第二维为列。这时P(O)为P[0][1];P(N)为P[1][0];…P(A)为P[3][3],以下为分阶段递推求解过程。 对于阶段2 P[1][1] = min{ P[0][1]+v[0][1], P[1][0]+h[1][0]} = min{3+1, 2+2} = 4 P[0][2] = P[0][1]+h[1][0] = 3+2 = 5 P[2][0] = P[1][0]+v[1][0] = 2+4 = 6 对于阶段3 P[1][2] = min{ P[0][2]+v[0][2], P[1][1]+h[1][1]} = min{5+3, 4+1} = 5 P[0][3] = P[0][2]+h[0][2] = 5+3 = 8 P[2][1] = min{ P[1][1]+v[1][1], P[2][0]+h[2][0]} = min{4+1, 6+1} = 5 P[3][0] = P[2][0]+v[2][0] = 6+1 = 7 对于阶段4 P[1][3] = min{ P[0][3]+v[0][3], P[1][2]+h[1][2]} = min{8+4, 5+4} = 9 P[2][2] = min{ P[1][2]+v[1][2], P[2][1]+h[2][1]} = min{5+2, 5+4} = 7 P[3][1] = min{ P[2][1]+v[2][1], P[3][0]+h[3][0]} = min{5+2, 7+3} = 7 对于阶段5 P[2][3] = min{ P[1][3]+v[1][3], P[2][2]+h[2][2]} = min{9+4, 7+5} = 12 P[3][2] = min{ P[2][2]+v[2][2], P[3][1]+h[3][1]} = min{7+2, 7+1} = 8 最后 P[3][3] = min{ P[2][3]+v[2][3], P[3][2]+h[3][2]} = min{12+3, 8+2} = 10 综上,数组P的通项表示为 P[i][j]= min( ( p[i-1][j]+v[i-1][j]), (p[i][j-1]+h[i][j-1]) ) (i, j>0) P[0][j]=P[0][j-1]+h[0][j-1]( i=0, j>0) P[i][0]=P[i-1][0]+v[i-1][0]( i>0, j=0) 下面给出P数组中的数据 数组P的通项表示为 P[i][j]= min( ( p[i-1][j]+v[i-1][j]), (p[i][j-1]+h[i][j-

    展开全文
  • #include#ifndef size_c#define size_c 200#endif // 预定义字符串的长度#define EQUAL 1 //EQUAL表示c[i][j]是由c[i-1][j-1]+1来的=此时两个序列有相同的字符#define UP 2 //UP表示c[i][j]是由c[i-1][j]来的=======...
  • } if (n->elem == 0) { *max = a + c; *min = b + d; } else { tmp[0] = a * c; tmp[1] = a * d; tmp[2] = b * c; tmp[3] = b * d; *max = tmp[0]; *min = tmp[0]; int i = 0; for (i=1; i; i++) { if (*max [i]) {...
  • 给定两个字符串 text1 和 text2,返回这两个字符串的最长公共子序列。一个字符串的 子序列是指这样一个新的字符串:它是由原字符串在不改变字符的相对顺序的情况下删除某些字符(也可以不删除任何字符)后组成的新字符...
  • 不为0时表明子问题已求解,直接返回结果,这种方法也叫备忘录方法,是动态规划的一种变形。 完整代码如下: #include #include #define MAXN 500 int dp[MAXN][MAXN]; int dpn(int n,int k){ if(dp[n][k]!=0) ...
  • 动态规划 用于求解最优化子问题的,往往是高效的而准确的。这背后的逻辑,其实就是程序设计的最基本原理——不要让程序做重复的事情。一句话说算法对于一个复杂的问题,可以分解成若干个子问题来解决,这是分治法。...
  • 算法描述 基于以上讨论可设计解多边形游戏问题的动态规划算法如下: void minMax(int i,int s,int j) { int e[5]; int a=m[i][s][0], b=m[i][s][1], r=(i+s-1)%n+1,//妙! c=m[r][j-s][0], d=m[r][j-s][1]; if(op[r]...
  • /**背包问题之动态规划解法结合营养套餐问题*author cg*date 2008 12 26/#include "stdio.h"#define N 6 /*定义食物数量*/#define S 100 /*最大营养大小*/int main() {int p[N] = {100,22,80,25,10};/*测试数据表示...
  • 一开始在接触动态规划的时候,可能会云里雾里,似乎能理解思路,但是又无法准确地表述或者把代码写出来。本篇将一步一步通过作图的方式帮助初次接触动态规划的同学来理解问题。这一篇将以经典的 01背包 问题为例子来...
  • 给定两个字符串text1 和text2,返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ,返回 0 。 一个字符串的子序列是指这样一个新的...二维动态规划问题。 假设字符串 text1和text2的长度分别为...
  • 动态规划思想

    2021-05-21 03:37:27
    1.简介动态规划(dynamic programming)是运筹学的一个分支,是求解决策过程(decision process)最优化的数学方法。20世纪50年代初美国数学家R.E.Bellman等人在研究多阶段决策过程(multistep decision process)的优化...
  • 然后用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...
  • 用两台处理机A和B处理n个作业。设第i个作业交给A处理需要时间ai...设计一个动态规划算法,使得这两台机器处理完这n个作业的时间最短。测试用例:6(任务数目)2 5 7 10 5 2(机器A处理这些任务的时间)3 8 4 11 3 4(机器...
  • } } //这一方程的求解要求对一切给定大小的集合S及S中的每个可能的元素k,计算 C(S,k)的值 //当S等于{2,3,...n}时,如果C(S,k)的值对k属于S都已经通过计算得到,则最优环游的最小费用为 //C(S,k)+d(k,1)中最小的...
  • 本学期的的算法实践课的实验作业。写的不好请大家多多指教。 【题目】 试设计一个算法,计算出从三角形的顶到底的一条路径,使该路径经过的数字总和最大。 数据输入: ... 由文件input.txt提供输入数据。...
  • 初识动态规划算法

    2021-05-21 07:57:59
    多阶段决策过程( multistep ... 动态规划 ( dynamic programming )算法 是解决 多阶段决策过程最优化问题 的一种常用方法,难度比较大,技巧性也很强。利用动态规划算法,可以优雅而高效地解决很多贪婪算法或...
  • #include#include#include#include#includeenum:int{MAXVALUE=999};templateclassBestTree{private:T**root;//记录给定子树的根节点.Ty**e;//记录子树概率总和.Type**w;//记录子树代价总和.std::vectorp;...
  • } } 动态规划: 1. 从最后一个往前选 2. 每次有两个选择:选,不选 3. 一直倒着往前,第一个是出口 求数组的前n项和(递归写法) 求数组的前n项和 { s u m ( a r r , n ) = s u m ( a r r , n − 1 ) + a r r [ n ...
  • 动态规划(01背包)

    2021-05-22 07:27:33
    动态规划这种方法把时间复杂度降到了O(n*T)。n是药品数,T是总时间。 首先开辟一个二维数组dp[n][T],dp[i][t]是指前i种药在时间t内的最大价值(0,0)和两个一维数组,一个是val[n],每种药品的价值,另一个是time[n...
  • 《01背包问题动态规划详解及c代码》由会员分享,可在线阅读,更多相关《01背包问题动态规划详解及c代码(5页珍藏版)》请在人人文库网上搜索。1、0/1背包问题动态规划详解及 C+弋码1问题描述给定一个载重量为C的背包有...
  • 动态规划算法实现数字图像压缩的研究维普资讯总第222期 计算机与数字工程 VOl_36NOq.42008年第 4期 Computer&Digital Engineering ...
  • 题目链接 #include <stdio.h> long long max (long long a, long long int b) { return (a > b) ? a : b; } int main() { int t, m; scanf("%d%d", &t, &m);... //注意这里.
  • Sample Input 5 2 5 3 1 4 Sample Output 5 13 0 8 0 思路:动态规划 +最长递增子序列思想 先将 数字序列每个长度的最长的递增子序列长度找到 例如 1 2 3 4 5 (下标) a[i] 2 5 3 1 4 dp[i] 1 2 2 1 3 dp[i]代表当前...
  • 该题是动态规划类型的题目,能划分成小问题取得最优值 2.观察其状态得状态转移方程: dp[i][j]=max(dp[i][j],dp[x][j-1] * num(x+1,i)) 其中dp[i][j]表示i个数字字符(为了方便表示)j个乘号所组成的最大值。 例如:...
  • 下面的简单问题说明了动态规划的基本原理。在字母表一∑上,分别给出两个长度为n和m的字符串A和B,确定在A和B中最长公共子序列的长度。这里,A = a₁a₂...an。的子序列是一个形式为a₁ka₂k...aik的字符串,其中每...
  • 这么简单的DP问题就不要再讲了吧...无奈楼翰诚大佬的数塔问题是在没讲清楚,也只好自己写一个...数塔问题嘛...已经有很多大佬讲过了,比如这位令人熟悉的大佬BUT!实际上关于这种从下往上的DP其实对于这道题完全可以...
  • 动态规划(dynamic programming)是运筹学的一个分支,是求解决策过程(decision process)最优化的数学方法。动态规划的难点就是思路:1、递归+记忆化 = 递推2、状态的定义:opt[n],dp[n]...3、状态转移方程:dp[n] = ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 159,778
精华内容 63,911
关键字:

动态规划c