01背包

最新推荐文章于 2025-05-20 22:23:34 发布

AC_coding

最新推荐文章于 2025-05-20 22:23:34 发布

阅读量298

点赞数

分类专栏： dp 文章标签： java 算法

本文链接：https://blog.csdn.net/Morandas/article/details/69945322

版权

dp 专栏收录该内容

5 篇文章

订阅专栏

import java.util.Scanner;

//01背包问题
public class test7 {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int c = sc.nextInt();
		int[][] dp = new int[n+1][c+1];
		
		int[] w = new int[n];
		int[] v = new int[n];
		for(int i=0;i<n;i++){
			w[i]=sc.nextInt();
			v[i]=sc.nextInt();
		}
		
		
		for(int i=0;i<n;i++){
			for(int j=0;j<=c;j++){
				if(j<w[i])
					dp[i+1][j]=dp[i][j];
				else
					dp[i+1][j]=Math.max(dp[i][j], dp[i][j-w[i]]+v[i]);
			}
		}
		System.out.println(dp[n][c]);
		
	}

}