1. #include 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=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 > 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]); // } // } // } //} ```

``` #include<bits/stdc++.h> using namespace std; int main() { int m,n; cin>>m>>n; int w[n+1];//称重 int v[n+1];//单个价值 int f[m+1]={0}; //最大价值 for(int i=1;i<=n;i++) { cin>>w[i]>>v[i]; } for(int i=1;i<=n;i++) { for(int j=m;j>=w[i];j--) { f[j]=max(f[j],f[j-w[i]]+v[i]); //判断是否选择i物品 } } cout<<f[m]; } ```