01背包 动态规划初级

解题思路:

注意事项:

参考代码:

import java.util.Scanner;

/**
 * 2021年2月23日  下午5:37:46
 * @author praguetramp
 * 01背包问题
 */
public class P1924 {
	//w[]物品重量,v[]物品价值,n物品数量,m背包容积
		private static int MaxValue(int w[],int v[],int n,int m) {
			//dp[n][m]表示前n件物品放在体积为m的背包下，形成的最大价值
			int dp[][] = new int[n+1][m+1];
			for(int i=1;i<=n;i++)
				for(int j=1;j<=m;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]);
				}
			return dp[n][m];
		}
		public static void main(String[] args) {
			Scanner in = new Scanner(System.in);
			int n=in.nextInt(),m=in.nextInt();
			int w[]=new int[n+1],v[]=new int[n+1];
			for(int i=1;i<=n;i++) {
				w[i]=in.nextInt();v[i]=in.nextInt();
			}
			int ans=MaxValue(w,v,n,m);
			System.out.println(ans);
			in.close();
		}
	}