找到最低成本路径 [英] To find the minimum cost path

问题描述

您将获得MxN matric。矩阵的每个单元都有相关的成本。最初你在（ 0 ， 0 ）你必须达到（M-1，N-1） ）。问题 从中找到最小成本路径（ 0 ， 0 ）到（M-1，N-1）以及最低成本。从细胞中，您只能移动到右侧细胞或向下细胞或对角线下部细胞。 
 
输入规格：
输入1：字符串数组，包含成本矩阵的行 as 元素。 
 input2：在成本矩阵中具有行数的整数。 
 
对于上面的例子，矩阵将是{5＃7＃2＃4,1＃8＃1＃3,6＃2＃9＃5,1＃6＃2＃8}和行数 4 。 
 
输出规格：
输出将是字符串，其中包含最小成本和由逗号分隔的路径。 
 
例如，给定成本矩阵
 
  5   7   2  4 
  1   8   1  3 
  6   2   9  5 
  1   6   2  8 
 
  1 ）最低成本 value    5 + 1 + 2 + 2 + 8 = 18 
  2 ）最低成本路径来自（ 0 ， 0 ，）到（M-1，N-1）  BDDR 
 
 B-  for  down move 
 D-对角线移动
 R-右移
 NA- N o解决方案
 
因此您的输出将是 18 ，BDDR 
 
方法签名：
 
  public   static   String  minimumCost（字符串 [] input1， int  input2）{
 
} 

下面是我试过的代码，但它输出为-86 BDDR，输出必须为18 BDDR < br $> b $ b

我的尝试：

＃包括stdafx.h
 #include< stdio.h> 
 #include< string.h> 
 //#include<conio.h> 
 #include< vector> 
 #include< string> 
 #include< iostream> 
 #include< sstream> 
 #include< stdlib.h> 
 #include< algorithm> 
 using namespace std; 
 #define arr input1 
 #define pb push_back 
 
 char * minimumCost（char * input1 []，int input2）
 {
 //编写代码这里
 vector<矢量<诠释> > v（input2），vc; 
 vector<矢量<串GT; > VS（输入2）; 
 int r = input2，i，t，j，c，minm; 
 for（i = 0; i< r;> {
j = 0; t = 0; c = 0; 
 while（arr [i] [j]！='\ 0'）
 {
 if（arr [i] [j] =='＃'）
 {
v [i] .pb（t）; 
t = 0; 
 c ++; 
} 
 else 
t = t * 10 + arr [i] [j]  - '0'; 
 j ++; 
} 
v [i] .pb（t）; 
} 
 c ++; 
 vc = v; 
 vs [0] .pb（\ 0）; 
 string str; 
 for（i = 1; i< r;> {
v [i] [0] + = v [i  -  1] [0]; 
 str = str +'B'; 
 vs [i] .pb（str）; 
} 
 str =; 
 for（i = 1; i< c; > {
v [0] [i] + = v [0] [i  -  1]; 
 str = str +'R'; 
 vs [0] .pb（str） ; 
} 
 for（i = 1; i< r;> {
 for（j = 1; j< c;> {
 
 // minm = min（v [i  -  1] [j  -  1]，min（v [i  -  1] [j]，v [i] [j  -  1]））; 
 minm = min（v [ i  -  1] [j  -  1]，min（v [i  -  1] [j]，v [i] [j  -  1]））; 
 if（v [i  -  1] [j  -  1 ] == minm）
 {
v [i] [j] + = v [i  -  1] [j  -  1]; 
 vs [i] .pb（vs [i  -  1] ] [j  -  1] +'B'）; 
 } 
 else if（v [i  -  1] [j] == minm）
 {
 v [i] [j] + = v [i  -  1] [j]; 
 vs [i] .pb（vs [i  -  1] [j] +'D'）; 
} 
其他
 {
 v [i] [j] + = v [i] [j  -  1]; 
 vs [i] .pb（vs [i] [j  -  1] +'R'）; 
} 
} 
} 
 ostringstream os; 
 os<< v [r  -  1] [c  -  1]; 
 printf（％d \ n，v [r  -  1] [c  -  1]）; 
 str = os.str（）+，+ vs [r  -  1] [c  -  1] +'\''; 
 cout<< str<< ENDL; 
 char * s =（char *）malloc（str.length（）+ 1）; 
 strcpy（s，str.c_str（））; 
 // printf（％s \ n，s）; 
返回s; 
} 
 int main（）
 {
 // char * arr [26] = {1＃3，4＃5，7＃12， 20＃23， 23＃24}; 
 // char * arr [26] = {1＃4，2＃3，3＃4}; 
 // char * arr [26] = {1＃2，1＃3，2＃3，3＃4，4＃7，5＃6， 4＃5}; 
 char * arr [100] = {5＃7＃2＃4，1＃8＃1＃3，6＃2＃9＃5，1＃6＃2＃8 }; 
 // char * arr [100] = {1＃7＃2＃4，1＃8＃1＃3，1＃9＃9＃5，1＃1＃1 ＃1\" }; 
 // minimumCost（arr，4）; 
 printf（％s \ n，minimumCost（arr，4））; 
 // _getche（）; 
} 

解决方案

您应该学习尽快使用调试器。而不是猜测你的代码在做什么，现在是时候看到你的代码执行并确保它完成你期望的。



调试器允许你跟踪执行逐行检查变量，你会看到它有一个停止做你期望的点。

调试器 - 维基百科，免费的百科全书 [ ^ ]

掌握Visual Studio 2010中的调试 - A初学者指南 [ ^ ]

http： //docs.oracle.com/javase/7/docs/technotes/tools/windows/jdb.html [ ^ ]

https://www.jetbrains.com/idea/help/debugging-your -first-java-application.html [ ^ ]



你知道正确的答案和获得它的路径。

使用调试器检查你的程序是否遵守计划的过程。

查看程序出错的地点和原因。


你能检查代码吗？已发布？

  for （i =  0 ; I< R;> 

you are given an MxN matric.Every cell of the matrix has a cost associated. initially you are at(0,0) and you have to reach (M-1,N-1). Question is to find the minimum cost path from (0,0) to (M-1,N-1) and also the minimum cost. From a cell you can only make a move to right cell or down cell or diagonally lower cell. 

Input Specification: 
Input1: A string array containing rows of the cost matrix as element. 
input2: An integer having number of rows in the cost matrix. 

For above example, the matrix would be {5#7#2#4,1#8#1#3,6#2#9#5,1#6#2#8} and number of rows would be 4. 

output Specification: 
The output will be a string containing minimum cost and the path chosen separated by the comma. 

For Example , Given the cost matrix 

5 7 2 4 
1 8 1 3 
6 2 9 5 
1 6 2 8 

1) minimum cost value is 5+1+2+2+8=18 
2) minimum cost path from (0,0,) to (M-1,N-1) is BDDR 

B- for down move 
D- Diagonal Move 
R- Right move 
NA- No solution 

Hence your output will be 18,BDDR 

method signature: 

public static String minimumCost(String[] input1, int input2) { 

}

Below is the code that i tried but it is giving me output as -86 BDDR whereas the output must be 18 BDDR

What I have tried:

#include "stdafx.h"
#include<stdio.h>
#include<string.h>
//#include<conio.h>
#include<vector>
#include<string>
#include<iostream>
#include<sstream>
#include<stdlib.h>
#include<algorithm>
using namespace std;
#define arr input1
#define pb push_back

char* minimumCost(char* input1[], int input2)
{
	//Write code here
	vector< vector<int> > v(input2), vc;
	vector< vector<string> > vs(input2);
	int r = input2, i, t, j, c, minm;
	for (i = 0; i<r;>	{
		j = 0; t = 0; c = 0;
		while (arr[i][j] != '\0')
		{
			if (arr[i][j] == '#')
			{
				v[i].pb(t);
				t = 0;
				c++;
			}
			else
				t = t * 10 + arr[i][j] - '0';
			j++;
		}
		v[i].pb(t);
	}
	c++;
	vc = v;
	vs[0].pb("\0");
	string str;
	for (i = 1; i<r;>	{
		v[i][0] += v[i - 1][0];
		str = str + 'B';
		vs[i].pb(str);
	}
	str = "";
	for (i = 1; i<c;>	{
		v[0][i] += v[0][i - 1];
		str = str + 'R';
		vs[0].pb(str);
	}
	for (i = 1; i<r;>	{
		for (j = 1; j<c;>		{
			
			//minm = min(v[i - 1][j - 1], min(v[i - 1][j], v[i][j - 1]));
			minm = min(v[i - 1][j - 1], min(v[i - 1][j], v[i][j - 1]));
			if (v[i - 1][j - 1] == minm)
			{
				v[i][j] += v[i - 1][j - 1];
				vs[i].pb(vs[i - 1][j - 1] + 'B');
			}
			else if (v[i - 1][j] == minm)
			{
				v[i][j] += v[i - 1][j];
				vs[i].pb(vs[i - 1][j] + 'D');
			}
			else
			{
				v[i][j] += v[i][j - 1];
				vs[i].pb(vs[i][j - 1] + 'R');
			}
		}
	}
	ostringstream os;
	os << v[r - 1][c - 1];
	printf("%d\n", v[r - 1][c - 1]);
	str = os.str() + "," + vs[r - 1][c - 1] + '\0';
	cout << str << endl;
	char *s = (char*)malloc(str.length() + 1);
	strcpy(s, str.c_str());
	//printf("%s\n",s);
	return s;
}
int main()
{
	//char *arr[26]={"1#3","4#5","7#12","20#23","23#24"};
	//char *arr[26]={"1#4","2#3","3#4"};
	//char *arr[26]={"1#2","1#3","2#3","3#4","4#7","5#6","4#5"};
	char *arr[100] = { "5#7#2#4", "1#8#1#3", "6#2#9#5", "1#6#2#8" };
	//char *arr[100]={"1#7#2#4","1#8#1#3","1#9#9#5","1#1#1#1"};
	//minimumCost(arr,4);
	printf("%s\n", minimumCost(arr, 4));
	//	_getche();
}

解决方案

You should learn to use the debugger as soon as possible. Rather than guessing what your code is doing, It is time to see your code executing and ensuring that it does what you expect.

The debugger allow you to follow the execution line by line, inspect variables and you will see that there is a point where it stop doing what you expect.
Debugger - Wikipedia, the free encyclopedia[^]
Mastering Debugging in Visual Studio 2010 - A Beginner's Guide[^]
http://docs.oracle.com/javase/7/docs/technotes/tools/windows/jdb.html[^]
https://www.jetbrains.com/idea/help/debugging-your-first-java-application.html[^]

You know the right answer and the path to get it.
Use the debugger to check that your program respects the planned process.
See where and why the program gets wrong.

Can you check the code you posted ?

for (i = 0; i<r;>

这篇关于找到最低成本路径的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！