01背包

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int V = scanner.nextInt();
        int N = scanner.nextInt();
        int[][] bag = new int[N][2];
        for(int i = 0; i < N; i++) {
            bag[i][0] = scanner.nextInt();
            bag[i][1] = scanner.nextInt();
        }
        int[] dp = new int[V+1];//背包容量为v最大能存放多少价值的物品dp[v]
        for(int i = 0; i < N; i++) {
            for(int j = V; j >= bag[i][0]; j--) {
                dp[j] = Math.max(dp[j], dp[j-bag[i][0]] + bag[i][1]); //比较，放不放物品i的价值
            }
        }
        System.out.println(dp[V]);
    }
}

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[nums + 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 + 1; i++){
            for(int j = 1; j <= capicaty; j++){
                if(w[i] > j){
                    dp[i][j] = dp[i - 1][j];
                }else{
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i]);
                }
            }
        }
        System.out.println(dp[nums][capicaty]);
    }
}