动态规划解决清楚易懂

解题思路:

注意事项:

参考代码:

import java.util.Scanner;

public class dp解决01背包问题 {

public static void main(String[] args) {

// TODO Auto-generated method stub

Scanner sc = new Scanner(System.in);

      int n = sc.nextInt();//物品的数量

      int m = sc.nextInt();//最大的装载重量

      int[] w = new int[n];

      int[] v = new int[n];

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

     w[i] = sc.nextInt();

     v[i] =sc.nextInt();

      }

      int res = dp(w,v,n,m);

      System.out.println(res);

}

public static int dp(int[] w,int[] v,int n,int m) {

int[][] dp = new int[n][m+1];

//初始化第一行数据

for(int i =0;i<=m;i++) {

if(i>=w[0]) {

dp[0][i] = v[0];

}else {

dp[0][i] = 0;

}

}

//算出其他行的数据

for(int row = 1;row<n;row++) {

for(int col = 0;col<=m;col++) {

if(col>=w[row]) {//背包的容量大于这个物品的重量

dp[row][col] = Math.max(v[row]+dp[row-1][col-w[row]], dp[row-1][col]);

}else {

dp[row][col] = dp[row-1][col];

}

}

}

return dp[n-1][m];

}

}