算法1

$O(n^2)$二维

import java.math.BigDecimal;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;
public class Main
{
    public static void main(String[] args)
    {
         Scanner scan=new Scanner(System.in);
         int a[][]=new  int[2000][2000];
         int f[][]=new int[2000][2000];
         int n=scan.nextInt();
         int m=scan.nextInt();
         int w[]=new int[1100];
         int v[]=new int[1100];
         for(int i=1;i<=m;++i) {
             w[i]=scan.nextInt();
             v[i]=scan.nextInt();
         }
         for(int i=1;i<=m;++i) {
             for(int j=0;j<=n;++j) {
                 f[i][j]=f[i-1][j];
                 if(j>=w[i]) {
                     f[i][j]=Math.max(f[i][j],f[i-1][j-w[i]]+v[i]);
                 }
             }
         }
         int res=0;
         for(int i=1;i<=n;++i) {
         res=Math.max(res,f[m][i]);
         }
         System.out.println(res);
    }
}

blablabla

### 算法2
#####  $O(n^2)$一维

----------

import java.math.BigDecimal;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;
public class Main
{
    public static void main(String[] args)
    {
         Scanner scan=new Scanner(System.in);
         int f[]=new int[2000];
         int n=scan.nextInt();
         int m=scan.nextInt();
         int w[]=new int[1100];
         int v[]=new int[1100];
         for(int i=1;i<=m;++i) {
             w[i]=scan.nextInt();
             v[i]=scan.nextInt();
         }
         for(int i=1;i<=m;++i) {
             for(int j=n;j>=0;--j) {
                 if(j>=w[i]) {
                     f[j]=Math.max(f[j],f[j-w[i]]+v[i]);
                 }
             }
         }
         System.out.println(f[n]);
    }
}

blablabla