背包问题

背包问题

背包问题主要是要求一个在有限范围内（你背包的体积范围内） 能够拿到最大值的问题。
最主要要想明白状态是由两个集合构成的就是两种状态，选第i个物品和不选。知道了整个到第i个物品时候你能够选到的最大值是由这两个状态组成的集合就可以了。

状态计算或者状态转移

状态计算/状态转移的方程实际上就是如何从之前的步骤计算到当前的步骤。这种背包问题就需要想到不拿当前物品，也就是dp[i-1][j] 和拿当前物品dp[i][j]。
dp[i][j] 是由前一个dp[i-1[j]转化而来的，这时候你需要判断一下当前j（也就是背包的容量是否够大，j>=v[i] 就代表当前的背包容量比当前物品的体积大，能够放得下，一开始这点我没想到。因为j是从0开始计算的，也就是说实际上他是从背包是满的状态开始计算的。一步步到最后背包最大时候的状态（是我的反向思维）这么做好像可以直接保证你在第二个for loop的时候里面dp[i][j-v[i]] 这个状态是计算过的，因为他会从大到小的放满背包。

import java.io.*;
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] s1 = br.readLine().split(" ");
        int N = Integer.parseInt(s1[0]), V = Integer.parseInt(s1[1]);
        int[] v = new int[N+1], w = new int[N+1];
        for (int i = 1; i <= N; i++) {
            s1 = br.readLine().split(" ");
            v[i] = Integer.parseInt(s1[0]);
            w[i] = Integer.parseInt(s1[1]);
        }
        int[][] dp = new int[N+1][V+1];
        for (int i = 1; i <= N; i++) {
            for (int j = 0; j <= V; j++) {
                dp[i][j] = dp[i-1][j];
                if (j >= v[i]) dp[i][j] = Math.max(dp[i][j], dp[i-1][j-v[i]] + w[i]);
            }
        }
        System.out.println(dp[N][V]);
    }
}