洛谷P2370 yyy2015c01 的 U 盘，Java题解，大量注释，包含完整的01背包状态转移方程说明

题目地址:https://www.luogu.com.cn/problem/P2370

有 n 件物品和一个最大承重为 W 的背包，每件物品的重量是 wi 、价值是 vi，在保证总重量不超过 W 的前提下，选择某些物品装入背包，背包的最大总价值是多少？每个物品只有 1 件，也就是每个物品只能选择 0 件或者 1 件。（ values 是价值数组，weights 是重量数组）

定义状态：dp(i, j) 是最大承重为 j、有前 i 件物品可选时的最大总价值

dp(i, j) = max { dp(i – 1, j), dp(i – 1, j – weights[i – 1]) + values[i – 1] }

for (int i = 1; i <= values.length; i++) {//i表示前i个物品
	for (int j = 1; j <= capacity; j++) {//j表示当前背包最大容量
		if(data[i-1]>j) {//该物品不可以装入背包
			dp[i][j]=dp[i-1][j];
		}else {//该物品可以装入背包
			dp[i][j]=Math.max(dp[i-1][j], dp[i-1][j-data[i-1]]+data[i-1]);
		}
	}
}

dp(j) = max { dp(j), dp(j – weights[i – 1]) + values[i – 1] } 注意(要逆向推导，具体如下)

for (int i = 1; i <=values.length; i++) {//i表示前i个物品
	//当j < weights[i-1],证明第i件物品不能选（必须要逆向推）
	for (int j = capacity; j >=weights[i-1]; j--) {
		dp[j]=Math.max(dp[j], dp[j-weights[i-1]]+values[i-1]);
	}
}	

排序：根据文件大小从小到大排序，大小相同则根据价值从大到小排序定义变量maxLen：最小需要的接口大小定义状态：dp[i][j]:是硬盘最大容量为 j、有前 i 件物品可选时的最大总价值，然后根据01背包的状态转移方程dp下去，并且不断更新maxLen（maxLen=max(maxLen, 第i个文件的大小)）

public class Main {
	
	public static void main(String[] args) {
		Scanner in=new Scanner(System.in);
		// n：文件数   p:期望最小价值	s:硬盘容量
		int n=in.nextInt(),p=in.nextInt(),s=in.nextInt();
		int[][] data=new int[n][2];
		for (int i = 0; i < n; i++) {
			data[i][0]=in.nextInt();//第 i 个文件的大小
			data[i][1]=in.nextInt();//第 i 个文件的价值
		}
		//排序：根据文件大小从小到大排序，大小相同则根据价值从大到小排序
		Arrays.sort(data,(o1,o2)->{
			if(o1[0]>o2[0]) {
				return 1;
			}else if (o1[0]dp[i-1][j])) {
					dp[i][j]=dp[i-1][j-data[i-1][0]]+data[i-1][1];
					maxLen=Math.max(maxLen, data[i-1][0]);
				}else {
					dp[i][j]=dp[i-1][j];
				}
				if(dp[i][j]>=p) {//价值超过了希望最小价值p，打印最小需要的接口大小并return
					System.out.println(maxLen);
					return;
				}
			}
		}	
		System.out.println("No Solution!");
	}
}