Question

简单java程序改错···

给定一个数字矩阵，现要求从该矩阵的每行中取出一个数字，且要求每行的这些数字的列编号是递增的，请设置程序，求出最优方案，使得这些取出的数字之和最大。如下例：3表示行，5表示列，然后在下面的3行5列每一行选一个数，使这3个数最大，要求选的数列数必须依次增大，就是从左上方向右下方选3个数使和最大。
以下是一个3行5列的矩阵，此最优值为：53，方案为：23-10-20
第一列 第二列 第三列 第四列 第五列
第一行： 7 23 -5 -24 16
第二行： 5 21 -4 10 23
第三行：-21 5 -4 -20 20
===================
package test;

public class rong {
static int [][]a,b;
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
System.out.println("输入行列数：");
int n=Utility.input();
int m=Utility.input();
a=new int [n][m];
b=new int [n][m];
System.out.println("输入矩阵：");
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
{a[i][j]=Utility.input();
b[i][j]=a[i][j];
}
for(int i=n-2;i>=0;i--)
for(int j=m-2;j>=0;j--)
{

int x=b[i+1][j+1];
for(int k=j+2;k<m;j++)
if(b[i+1][k]>x)
x=b[i+1][k];
b[i][j]+=x;
}
int x=b[0][0];
for(int i=1;i<m;i++)
{

if(b[0][i]>x)
x=b[0][i];
}
System.out.println(x);
}

}
============================
package test;

import java.util.Scanner;

public class Utility {

public static int input() {
// TODO Auto-generated method stub
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
return n;
}

}

Answer 1

这个算法，我觉得是这样的：
首先，列数肯定要大于行数
其次吧，以这个3行5列为例，可以分两步做：
第一步，0-4这5个数里，任取3个不同的，求出所有的取法，并且按升序排列
第二步就简单了，根据刚刚求出的所有取法，对号入座取每一行对应的数进行累加
最后把所有累加的数，求一个最大呗。

Answer 2

跟我做过的一个ACM的动态规划的题目基本一致，贴上我的代码你看看~
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner s = new Scanner(System.in);
int f = 3;
int v = 5;
int[][] p = new int[f][v];
int[][] c = new int[f][v];
for (int i = 0; i < f; i++)
for (int j = 0; j < v; j++)
p[i][j] = s.nextInt();
for (int k = 0; k < v; k++)
c[0][k] = p[0][k];
for (int a = 1; a < f; a++)
for (int b = a; b < v; b++) {
int max = -9999999;
for (int x = 0; x < b; x++) {
if (c[a - 1][x] > max)
max = c[a - 1][x];
c[a][b] = p[a][b] + max;
}
}
int max = -99999;
for (int y = f; y < v; y++)
if (c[f - 1][y] > max)
max = c[f - 1][y];
System.out.println(max);
}
}
望能解决你的问题，且追加分~~

Answer 3

这个算法很有意思，如果你给加分的话，我就帮你想想

追问

只要回答出来，可以追加分数...