01背包

解析：动态规划。1，dp[i][j]为背包容量为j时装前i个的最大价值。所求的是dp[5][9]。2，初始化数据，因为i=1时，只要j>w[i]就能装第一个，所以是v[i]。当j=0时，直接为0。3，递推关系式，当装的动第i个(j>w[i])时，dp[i][j] = max(dp[i-1][j],dp[i-1][j-w[i]]+v[i])(拿第i个与不拿第i个)。当装不动第i个时候(j<w[i]),dp[i][j]=dp[i-1][j]

import java.util.Scanner;
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int capicaty = sc.nextInt();//总容量
        int nums = sc.nextInt();
        int[] w = new int[capicaty + 1];//质量数组
        int[] v = new int[nums + 1];//价值数组
        for(int i = 1; i < nums + 1; i++){
            w[i] = sc.nextInt();
            v[i] = sc.nextInt();
        }
        int[][] dp = new int[nums+1][capicaty+1];
        for(int i=1;i<=nums;i++){
            for(int j=0;j<=capicaty;j++){
                if(j<w[i]){//如果背包容量不够装第i件
                    dp[i][j] = dp[i-1][j];//最大价值等于偷前一件时候的
                }else{//如果背包容量够装第i件
                    if(i==1){
                        dp[i][j] = v[i];
                    }else{
                          dp[i][j] = Math.max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]);//最大价值等于前一件与偷这一件(i-1,j-w(i))的最大值
                    }
                    }
            }
        }
       System.out.println(dp[nums][capicaty]);
    }
}