动态规划之背包问题（java)全面总结

动态规划之背包问题(java)全面总结

总结整理不易，如果对你有所帮助，不妨动手点个免费的赞哦，收藏关注不迷路[比心]~

1. 01背包

有一个体积为V的背包，商店有n个物品，每个物品有一个价值v和体积w，每个物品只能被拿一次，问能够装下物品的最大价值。

这里每一种物品只有两种状态即“拿”或“不拿”设状态dp[i][j]表示到第i个物品为止，拿的物品总体积为j的情况下的最大价值。

我们并不关心某个物品有没有被拿，只关心当前体积下的最大价值。

转移方程为:

dp[i][j]= max(dp[i][j],dp[i-1][j-w]+v);

如果不拿物品i，那么最大价值就是dp[i-1][j]，如果拿了就是从体积j-v转移过来，体积会变大w，价值增加v。最后输出dp[n][V];

例题：

小明的背包1

题目描述

小明有一个容量为 V 的背包。

这天他去商场购物，商场一共有N 件物品，第 i 件物品的体积为 wi，价值为 vi。

小明想知道在购买的物品总体积不超过 V的情况下所能获得的最大价值为多少，请你帮他算算。

输入描述

输入第 11 行包含两个正整数 N,V，表示商场物品的数量和小明的背包容量。

第 2∼N+1 行包含 2 个正整数 w,v，表示物品的体积和价值。

1≤N≤100 ,1≤V≤1000,≤wi,vi≤10000。

输出描述

输出一行整数表示小明所能获得的最大价值。

输入输出样例

示例 1

输入

5 201 62 53 85 153 3 

输出

37

运行限制

• 最大运行时间：1s
• 最大运行内存: 128M

  import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);int n = sc.nextInt(); // 商场物品的数量int m = sc.nextInt(); // 小明的背包容量int[] w = new int[n]; // 用于存储物品的体积int[] v = new int[n]; // 用于存储物品的价值// 输入每件物品的体积和价值for(int i = 0; i = w[i - 1] + k) {                    dp[1][j] = Math.max(dp[0][j - w[i - 1] - k] + 2 * v[i - 1], dp[1][j]);                }            }        }        // 输出最大价值，选择不使用魔法和使用魔法的最大值        System.out.println(Math.max(dp[0][m], dp[1][m]));    }}

  2. 完全背包

  完全背包也叫无穷背包，即每种物品有无数个的背包。

  有一个体积为V的背包，商店有n个物品，每个物品有一个价值v和体积w，每个物品有无限多个，可以被拿无穷次，问能够装下物品的最大价值。

  这里每一种物品只有无穷种状态即“拿0个、1个、2个…无穷多个”

  设状态dp[i]表示拿的物品总体积为i的情况下的最大价值。

  我们并不关心某个物品拿了几个，只关心当前体积下的最大价值。

  转移方程为:dp[i]=max(dp[i],dp[i-w]+v)，现在就必须使用“新数据”来更新“新数据”因为新数据中包括了拿当前这个物品的状态，而当前这个物品是可以被拿无数次的。

  最后输出dp[V]即可。

  例题：

  小明的背包2

  题目描述

  小明有一个容量为V的背包。

  这天他去商场购物，商场一共有 N 种物品，第 i 种物品的体积为 wi，价值为 vi，每种物品都有无限多个。

  小明想知道在购买的物品总体积不超过 V的情况下所能获得的最大价值为多少，请你帮他算算。

  输入描述

  输入第 11 行包含两个正整数N,V，表示商场物品的数量和小明的背包容量。

  第2∼N+1 行包含 22 个正整数 w,v，表示物品的体积和价值。

  1≤N≤1000，1≤V≤10000，1≤wi,vi≤1000。

  输出描述

  输出一行整数表示小明所能获得的最大价值。

  输入输出样例

  示例 1

  输入

  5 201 62 53 85 153 3 

  输出

  120

  运行限制

  • 最大运行时间：1s
  • 最大运行内存: 256M

    import java.util.Scanner;public class Main {    public static void main(String[] args) {        Scanner sc = new Scanner(System.in);         int n = sc.nextInt(); // 物品数量        int m = sc.nextInt(); // 背包容量        int[] w = new int[n]; // 物品体积数组        int[] v = new int[n]; // 物品价值数组        // 输入每种物品的体积和价值        for (int i = 0; i