用动态规划法求总和最大的路径 问题如下（求详细程序代码）

令f[i][j]表示从第i行第j个数走到底所能得到的最小和，则有：

f[i][j]=min(f[i+1][j],f[i+1][j+1])+a[i][j]，式中a[i][j]为第i行第j个数的值，最后一行f[i][j]=a[i][j]，则f[1][1]即为答案

//==

#include <iostream>

using namespace std;

#include <cmath>

//--

struct Coordinate //顶点

{

float x;

float y;

};

//--

float Module(Coordinate a,Coordinate b) //求两点的模值

{

float module=(ax-bx)(ax-bx)+(ay-by)(ay-by);

return (float)sqrt(module);

}

//--

float W(Coordinate a,Coordinate b,Coordinate c) //权函数

{

return Module(a,b)+Module(b,c)+Module(a,c);

}

//--

void Triangle_Dissect(Coordinate v[11],float m[10][10],int s[10][10],int n) //最优剖分

{

for(int i=1;i<n;i++)

{

m[i][i]=0;

}

for(int l=2;l<=n-1;l++)

{

for(i=1;i<=n-l;i++)

{

int j=i+l-1;

m[i][j]=m[i+1][j]+W(v[i-1],v[i],v[j]);

s[i][j]=i;

for(int k=i;k<=j-1;k++)

{

float q=m[i][k]+m[k+1][j]+W(v[i-1],v[k],v[j]);

if(q<m[i][j])

{

m[i][j]=q;

s[i][j]=k;

}

}

}

}

}

//--

bool judge(Coordinate a,Coordinate b,Coordinate v[11],int n) //判断能否构成凸多边形

{

float t[11];

int j=0;

int k=0;

for(int i=0;i<n;i++)

{

if(ax==bx)

t[i]=v[i]x-ax;

else if(ay==by)

t[i]=v[i]y-ay;

else

t[i]=(v[i]y-ay)/(by-ay)-(v[i]x-ax)/(bx-ax);

}

for(i=0;i<n;i++)

{

if(t[i]>0)

j++;

if(t[i]<0)

k++;

}

if(j==n-2||k==n-2)

return true;

else

return false;

}

//--

bool input(Coordinate v[11],int n) //输入顶点坐标，并判断能否构成凸多边形

{

for(int i=0;i<n;i++)

{

cout<<"输入顶点v"<<i<<"坐标";

cin>>v[i]x>>v[i]y;

}

int t[11];

for(i=0;i<n;i++)

{

if(i==n-1)

t[i]=judge(v[i],v[0],v,n);

else

t[i]=judge(v[i],v[i+1],v,n);

}

int j=0;

for(i=0;i<n;i++)

{

if(t[i]>0)

j++;

}

if(j==n)

return true;

else

return false;

}

//--

void outputm(float a[10][10],int n) //输出数组m中保存的数据

{

for(int i=1;i<n;i++)

{

for(int j=1;j<n;j++)

{

if(j<i)

{

coutwidth(16);

cout<<"";

}

else

{

coutwidth(16);

cout<<a[i][j];

}

}

cout<<endl;

}

}

//--

void outputs(int a[10][10],int n) //输出数组s中保存的数据

{

for(int i=1;i<n;i++)

{

for(int j=1;j<n;j++)

{

if(j<=i)

{

coutwidth(12);

cout<<"";

}

else

{

coutwidth(12);

cout<<a[i][j];

}

}

cout<<endl;

}

}

//--

void Triangle_Print(int i,int j,int s[10][10]) //输出最优剖分出的全部三角形

{

if(i==j)

return;

Triangle_Print(i,s[i][j],s);

Triangle_Print(s[i][j]+1,j,s);

cout<<"三角形:v"<<i-1<<"v"<<s[i][j]<<"v"<<j<<endl;

}

//--

void main()

{

int n;

Coordinate v[11];

float m[10][10];

int s[10][10];

cout<<"输入顶点个数，限定10个"<<endl;

cin>>n;

if(n>10)

cout<<"输入有误"<<endl;

else

{

cout<<"输入各顶点坐标"<<endl;

if(input(v,n))

{

Triangle_Dissect(v,m,s,n);

cout<<endl<<"数组m中记录的数据为:"<<endl;

outputm(m,n);

cout<<"数组s中记录的数据为:"<<endl;

outputs(s,n);

cout<<"最优凸多边形三角剖分为："<<endl;

Triangle_Print(1,n-1,s);

}

else

cout<<"不能构成凸多边形"<<endl;

}

}

//===

呵呵 这类问题好难 写了一整天啊 学到了很多 还是有收获的

以前写的 自己看吧

#include<stdioh>

int w[5]={0,3,5,2,1},p[5]={0,9,10,7,4};

int c=7,n=4;

int cw=0,cp=0,bestp=0;

int x[10]={0};

void try(int k)

{

int i;

if(k>n)

{

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

printf("%2d",x[i]);

printf(" %d %d\n",cw,cp);

if(bestp<cp)

bestp=cp;

}

else

{

x[k]=1;

cw=cw+w[k];

cp=cp+p[k];

if(cw<=c)

try(k+1);

x[k]=0;

cw=cw-w[k];

cp=cp-p[k];

if(cw<=c)

try(k+1);

}

}

main()

{

clrscr();

try(1);

printf("best_P=%d",bestp);

}

不是我不想帮你，但如果真要改的话，整个程序差不多要重写了……首先你要确定此程序是上网刷题/比赛？还是自学算法知识？如果你有很好的数学功底还可以自学知识，但比赛的话自学是绝对不够的，那需要充分的交流，还有，养成良好的编程风格是一个极其重要的方面，在网上应该可以找到某些大牛的代码集，运气好还有注释版的，可以多多借鉴。下面是一段代码，NetBeans/G++编译通过，你可以尝试改成类结构的。^_^

#include <iostream>

using namespace std;

#define MAXLENGTH 20

// 这是偷懒的部分……不要介意哈

int maxLength[MAXLENGTH + 2][MAXLENGTH + 2];

int preChar[MAXLENGTH + 2][MAXLENGTH + 2];

/

参数说明

s1：待处理字符串1

s2：待处理字符串2

l1：s1长度（不包括字符串结束符'/0'）

l2：s2长度（不包括字符串结束符'/0'）

参数中加const的目的是为了保护外部数据，防止因失误而在函数内部改变了本因无需改变的数值。

/

int LCSLength(const char s1, const int l1, const char s2, const int l2) {

/ 尽量不要在for等语句中定义变量，每个函数一开始最好就把需要的变量全部定义好，同时尽量赋予有意义的函数名 /

/ 当然，有时偷点懒是可以的，但你要确保过了几个月后一看到代码就能很快知道这是啥意思 /

int i, j;

/ maxLength用于存放中间数据，意义：maxLength[i][j]表示：s1前i个字符与s2前j个字符的最长子序列长度

preChar用于存放当前最长子序列是由那一个自序列得来的

因本算法特殊性，需要各额外2位的存储空间

/

//

for (i = 0; i <= l1; i++) maxLength[i][0] = 0;

for (j = 0; j <= l2; j++) maxLength[0][j] = 0;

for (i = 0; i <= l1; i++)

for (j = 0; j <= l2; j++) {

/ 如果s1第i个字符与s2第j个字符相同，则更新maxLength[i+1][j+1]存储的最大值，和preChar存放的前缀自序列位置

下同

/

if (s1[i] == s2[j] && maxLength[i + 1][j + 1] < maxLength[i][j] + 1) {

maxLength[i + 1][j + 1] = maxLength[i][j] + 1;

preChar[i + 1][j + 1] = 1;

}

if (maxLength[i + 1][j] < maxLength[i][j]) {

maxLength[i + 1][j] = maxLength[i][j];

preChar[i + 1][j] = 2;

}

if (maxLength[i][j + 1] < maxLength[i][j]) {

maxLength[i][j + 1] = maxLength[i][j];

preChar[i][j + 1] = 3;

}

}

/ 返回最长子序列长度 /

return maxLength[l1][l2];

}

/

s1、s2与上同

i：s1当前字符序号

j：s2当前字符序号

i、j初始值为各自字符串长度

/

void LCSOutput(const char s1, const int i, const char s2, const int j) {

if (i >= 0 && j >= 0) {

// 由于是逆向输出，所以先递归，后输出

switch (preChar[i][j]) {

case 1:

LCSOutput(s1, i - 1, s2, j - 1);

break;

case 2:

LCSOutput(s1, i - 1, s2, j);

break;

case 3:

LCSOutput(s1, i, s2, j - 1);

break;

default:

break;

}

if (s1[i] == s2[j])

cout << s1[i];

}

}

int main() {

cout << "最长公共子序列长度：" << LCSLength("1234567890", 10, "1358967", 7) << endl;

cout << "最长公共子序列（不确保唯一）：";

LCSOutput("1234567890", 10, "1358967", 7);

cout << endl;

return 0;

}

#include <stdioh>

int list[200][200];

int x[15];

int n;

int c;

int s;

int max (int a,int b)

{

if(a>b)return a;

else return b;

}

int ks(int n,int weight[],int value[],int x[],int c)

{

int i,j;

for(i=0;i<=n;i++)

list[i][0]=0;

for(j=0;j<=c;j++)

list[0][i]=0;

for(i=0;i<=n-1;i++)

for(j=0;j<=c;j++)

if(j<weight[i])

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

else

list[i][j]=max(list[i-1][j],list[i-1][j-weight[i]]+value[i]);

j=c;

for(i=n-1;i>=0;i--){

if(list[i][j]>list[i-1][j]){

x[i]=1;

j=j-weight[i];

}else x[i]=0;

}

printf("背包中的物品序列号:\n");

for(i=0;i<n;i++)

printf("%d\n",x[i]);

return list[n-1][c]; }

void main(){

int weight[15]={2,2,6,5,4};

int value[15]={6,3,5,4,6};

c=10;

n=5;

s=ks(n,weight,value,x,c);

printf("背包中的总价值:\n");

printf("%d\n",s);

}

1．0-1背包： 每个背包只能使用一次或有限次(可转化为一次)：

A求最多可放入的重量。

NOIP2001 装箱问题

有一个箱子容量为v(正整数，o≤v≤20000)，同时有n个物品(o≤n≤30)，每个物品有一个体积 (正整数)。要求从 n 个物品中，任取若千个装入箱内，使箱子的剩余空间为最小。

l 搜索方法

procedure search(k,v:integer);

var i,j:integer;

begin

if v<best then best:=v;

if v-(s[n]-s[k-1])>=best then exit;

if k<=n then begin

if v>w[k] then search(k+1,v-w[k]);

search(k+1,v);

end;

end;

l DP

F[I,j]为前i个物品中选择若干个放入使其体积正好为j的标志，为布尔型。

实现:将最优化问题转化为判定性问题

f [I, j] = f [ i-1, j-w[i] ] (w[I]<=j<=v) 边界：f[0,0]:=true

For I:=1 to n do

For j:=w[I] to v do F[I,j]:=f[I-1,j-w[I]];

优化：当前状态只与前一阶段状态有关，可降至一维。

F[0]:=true;

For I:=1 to n do begin

F1:=f;

For j:=w[I] to v do

If f[j-w[I]] then f1[j]:=true;

F:=f1;

End;

B求可以放入的最大价值。

F[I,j] 为容量为I时取前j个背包所能获得的最大价值。

F [i,j] = max

C求恰好装满的情况数。

DP:

Procedure update;

var j,k:integer;

begin

c:=a;

for j:=0 to n do

if a[j]>0 then

if j+now<=n then inc(c[j+now],a[j]);

a:=c;

end;

2．可重复背包

A求最多可放入的重量。

F[I,j]为前i个物品中选择若干个放入使其体积正好为j的标志，为布尔型。

状态转移方程为

f[I,j] = f [ I-1, j – w[I]k ] (k=1 j div w[I])

B求可以放入的最大价值。

USACO 12 Score Inflation

进行一次竞赛，总时间T固定，有若干种可选择的题目，每种题目可选入的数量不限，每种题目有一个ti（解答此题所需的时间）和一个si（解答此题所得的分数），现要选择若干题目，使解这些题的总时间在T以内的前提下，所得的总分最大，求最大的得分。

易想到：

f[i,j] = max (0<=k<= i div w[j])

其中f[i,j]表示容量为i时取前j种背包所能达到的最大值。

实现：

Begin

FillChar(f,SizeOf(f),0);

For i:=1 To M Do

For j:=1 To N Do

If i-problem[j]time>=0 Then

Begin

t:=problem[j]point+f[i-problem[j]time];

If t>f[i] Then f[i]:=t;

End;

Writeln(f[M]);

End

C求恰好装满的情况数。

Ahoi2001 Problem2

求自然数n本质不同的质数和的表达式的数目。

思路一，生成每个质数的系数的排列，在一一测试，这是通法。

procedure try(dep:integer);

var i,j:integer;

begin

cal;

if now>n then exit;

if dep=l+1 then begin

cal;

if now=n then inc(tot);

exit;

end;

for i:=0 to n div pr[dep] do begin

xs[dep]:=i;

try(dep+1);

xs[dep]:=0;

end;

end;

思路二，递归搜索效率较高

procedure try(dep,rest:integer);

var i,j,x:integer;

begin

if (rest<=0) or (dep=l+1) then begin

if rest=0 then inc(tot);

exit;

end;

for i:=0 to rest div pr[dep] do

try(dep+1,rest-pr[dep]i);

end;

思路三：可使用动态规划求解

USACO12 money system

V个物品，背包容量为n，求放法总数。

转移方程：

Procedure update;

var j,k:integer;

begin

c:=a;

for j:=0 to n do

if a[j]>0 then

for k:=1 to n div now do

if j+nowk<=n then inc(c[j+nowk],a[j]);

a:=c;

end;

begin

read(now);

i:=0;

while i<=n do begin

a[i]:=1; inc(i,now); end;

for i:=2 to v do

begin

read(now);

update;

end;

writeln(a[n]);

f[i],表示前i个字符是否是对话。f[0]=true

然后一位一位往后推，若最后几位匹配某个单词就可以继承

eg:f[3]=true copy(s,4,3)='one'那么f[6]=true

注意不要用copy会超时

直接一位一位判断 s[i-1]='e' s[i-2]='n' s[i-3]='o' 就继承

以上就是关于用动态规划法求总和最大的路径 问题如下（求详细程序代码）全部的内容，包括:用动态规划法求总和最大的路径 问题如下（求详细程序代码）、用C++编写程序 动态规划、C语言动态规划——0-1背包问题等相关内容解答，如果想了解更多相关内容，可以关注我们，你们的支持是我们更新的动力！