背包九讲

（1） 0-1背包问题

题目链接：https://www.acwing.com/problem/content/2/

思路：动态规划求解

• 变量
  • dp[i][j] 记录前i个物品在体积为j的情况下的最大价值
  • v[i]：第i个物品的体积
  • w[i]：第i个物品的价值
• 状态方程
  • 选第i个物品：dp[i][j] = dp[i-1][j-v[i]] + w[i]
  • 不选第i个物品：dp[i][j] = dp[i-1][j]

代码如下：

import java.util.Scanner;

public class Main{

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in );



        int n = in.nextInt();
        int m = in.nextInt();

        //int[][] dp = new int[n+1][m+1];

        int[] dp = new int[m+1];

        int[] w = new int[n+1];
        int[] v = new int[n+1];

        for(int i = 1;i<=n;i++){

            v[i] = in.nextInt();
            w[i] = in.nextInt();
        }

        for(int i = 1;i<=n;i++){
            for(int j = m;j>=v[i];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]);
//                }
                dp[j] = Math.max(dp[j],dp[j-v[i]] + w[i]);
            }
        }

        System.out.println(dp[m]);
    }

}

（2）完全背包问题

题目跟先前的一样，只是增加了每一个物品可以多选的条件。