学习笔记-背包问题

如果有一个表格类型的地图，上面分布着不同价格的物品，要求从左上角走到右下角，求能够拿到的价格最大是多少？

如图，其中的数字为在（i，j）位置的物品的位置

想法；

建立一个数组，大小为（比输入的m和n均大一）

数组存入

for(int i=0;i<=m;i++){
for(int j=0;j<=n;j++){
if(i==m||j==n){
s[i][j]=Integer.MIN_VALUE;
}else{
s[i][j]=cin.nextInt();
}
}
}

就是将原来的地图变化为

然后进行查找

for(int i=m-1;i>=0;i--){
for(int j=n-1;j>=0;j--){
if(i!=m-1||j!=n-1){
s[i][j]+=Math.max(s[i+1][j], s[i][j+1]);
}
}
}

此时最大就时（0,0）位置的价值，输出即可

全部代码如下

import java.util.*;

public class Main {

public static void main(String[] args) {
Scanner cin = new Scanner(System.in);
int id = 1;
while(cin.hasNext()){

int m = cin.nextInt();
int n = cin.nextInt();
if(m==0 && n==0)break;
int s[][] = new int[m+1][n+1];

for(int i=0;i<=m;i++){
for(int j=0;j<=n;j++){
if(i==m||j==n){
s[i][j]=Integer.MIN_VALUE;
}else{
s[i][j]=cin.nextInt();
}
}
}

for(int i=m-1;i>=0;i--){
for(int j=n-1;j>=0;j--){
if(i!=m-1||j!=n-1){
s[i][j]+=Math.max(s[i+1][j], s[i][j+1]);
}
}
}

System.out.println("Case #"+ id++ +":"+s[0][0]);
}
cin.close();
}
}