题解 | 【模板】01背包

import java.util.Arrays;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner scanner=new Scanner(System.in);
		int n=scanner.nextInt();
		int V=scanner.nextInt();
		int v[]=new int[n];
		int w[]=new int[n];
		for (int i = 0; i < w.length; i++) {
			v[i]=scanner.nextInt();//体积
			w[i]=scanner.nextInt();//价值
		}
		/*
		 * int dp[][]=new int[n][V+1];//dp[i][j]表示在体积为j的情况下，考虑是否装第i件物品，使得价值最大 //初始化 for
		 * (int i = 0; i < dp.length; i++) { dp[i][0]=0; } for (int j = 0; j < V+1; j++)
		 * { if(j>=v[0])dp[0][j]=w[0]; } for (int i = 1; i < n; i++) { for (int j = 1; j
		 * < V+1; j++) { if(j>=v[i]) { dp[i][j]=Math.max(dp[i-1][j-v[i]]+w[i],
		 * dp[i-1][j]); }else { dp[i][j]=dp[i-1][j]; }
		 * 
		 * } } System.out.println(dp[n-1][V]);
		 */
		//不要求全部装满
		int dp1[]=new int[V+1];
		for (int i = 0; i < n ; i++) {
			for (int j = V; j >= v[i]; j--) {
				dp1[j]=Math.max(dp1[j], dp1[j-v[i]]+w[i]);
			}
		}
		System.out.println(dp1[V]);
		
		
		//下面计算要求背包恰好装满的最大价值
		long dp2[]=new long[V+1];
		Arrays.fill(dp2, -1);//负数表示无法恰好装满
		dp2[0]=0;//初始化，容量为0肯定能装满
		for (int i = 0; i < n; i++) {
			for (int j = V; j >= v[i]; j--) {
				if(dp2[j-v[i]]!=-1) {
					dp2[j]=Math.max(dp2[j-v[i]]+w[i], dp2[j]);
				}
			}
		}
		if(dp2[V]!=-1) {
			System.out.println(dp2[V]);
		}else {
			System.out.println(0);
		}
		
		
		

	}

}

01背包我之前只会二维dp版的，没想到还有一维dp优化版，首先讲一下不要求恰好装满的情况，我们创建一维dp1数组，dp1[j]表示在容量为j的情况下，能装的最大价值。dp1[j]=Math.max(dp1[j], dp1[j-v[i]]+w[i]);循环中j要求逆序，也就是i从V+1到v[i]，这样才能保证后面的结果不会把前面的结果覆盖。

要求恰好装满的情况，我们先把dp2的所有元素赋为-1，然后把dp[0]赋值为0，因为当容量为0时，一定能恰好装满，且价值为0。后买如果dp2[j-v[i]]不等于-1，也就是那个容量下就已经能装满了，我现在恰好给它增加v[i]的容量，那肯定也可以装满v[i]