完全背包问题

解题思路:

注意事项:

参考代码:

import java.util.Scanner;

public class 背包 {

/**

* @param args

*/

public static void main(String[] args) {

       // TODO Auto-generated method stub

        Scanner sc = new Scanner(System.in);

        int m=sc.nextInt();

        int n=sc.nextInt();

        int[][] wi=new int[n+1][2];

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

            wi[i][0]=sc.nextInt();///重量

            wi[i][1]=sc.nextInt();//质量

        }

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

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

            for (int j = 1; j <=m; j++) {

                if (wi[i][0]>j) {

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

                }else {

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

                }

            }

        }

        System.out.println("max="+dp[n][m]);

}

}