想了半天 动态规划

解题思路:

注意事项:

参考代码:

public class a5 {

/**

* @param args

*/

public static void main(String[] args) {

// TODO Auto-generated method stub

Scanner scanner=new Scanner(System.in);

int a=scanner.nextInt(),b=scanner.nextInt();

int dp[][]=new int [a+1][b+1];// 背包问题前面都是空的 所以要浪费一行所以要+1

int v[]=new int[a+1];

int t[]=new int[a+1] ;

for (int i = 1; i <=a; i++) {

v[i]=scanner.nextInt();

t[i]=scanner.nextInt();

}

for (int i = 1; i <=a; i++) //遍历所装物品{

for (int j = 1; j<=b; j++)///遍历质量

{

if (j>=v[i]) {//背包体积必须大于=物品体积

dp[i][j]=Math.max(dp[i-1][j], dp[i-1][j-v[i]]+t[i]);

//比较之前的价值与现在的价值

//动态规划

}

else {

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

}

}

System.out.println(dp[a][b]);

}

}