1. #include <bits/stdc++.h> using namespace std; const int N = 201; int mem[N][N]; int v[N], w[N]; int n, m;//n是物品，m是重量 int dfs(int x, int spv) { if(mem[x][spv])return mem[x][spv]; int sum=0; if(x>n)return sum =0; if(spv<v[x])sum=dfs(x+1,spv); else if(spv>=v[x]){ sum=max(dfs(x+1,spv),dfs(x+1,spv-v[x])+w[x]); } mem[x][spv]=sum; return sum; } int main() { cin >> m >> n; for (int i = 1; i <= n; i++) { cin >> v[i] >> w[i]; } memset(mem, 0, sizeof mem); int ans = dfs(1, m); cout << ans; return 0; }

import  java.util.*;
public class Main{
    static int N, m;
    static int v[];
    static int w[];
    static int res = 0;

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);

        m = scan.nextInt();//背包容量
        N = scan.nextInt(); //N件物品
        w = new int[N + 1]; //物品的体积
        v = new int[N + 1];//物品所占的价值
        for (int i = 1; i <= N; i++) {
            w[i] = scan.nextInt();//物品的体积
            v[i] = scan.nextInt();//物品所占的价值
        }
//        System.out.println(dfs(1,m));
        //一维写法;
        int dp[] = new int[m + 1];
        for (int i = 1; i <= N; i++) {
            //从后往前遍历的原因是,dp[j]是dp[j-w[i]]的后一个状态;
            for (int j = m; j >= w[i]; j--) {//容量能装下wi;
                dp[j] = Math.max(dp[j], dp[j - w[i]] + v[i]);
            }
        }
        System.out.println(dp[m]);
    }
}
//        //        int dp[][]=new int[N+1][m+1];
//        //二维写法,i为物品个数,j为体积;
////        for(int i=1;i<=N;i++){
////          for (int j=1;j<=m;j++){
////              if(j<w[i]){  //如果当前面积装不下w[i]件物品
////                  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[N][m]);
//        }
                            dfs写法 
//    private static int dfs(int x,int spy) {
//        if(x>N){
//            return 0;
//        }else{
//            if(spy<w[x]){ //当前背包容量装不下w[x]
//                return dfs(x+1,spy);
//            }else {
//                return Math.max(dfs(x+1,spy),dfs(x+1,spy-w[x])+v[x]);
//            }
//        }
//    }
//}