题目：

• 有 N 种物品和一个容量是 V 的背包，每种物品都有无限件可用。第 i 种物品的体积是 vi，价值是 wi。

求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。

输出最大价值。

输入格式：第一行两个整数，N，V，用空格隔开，分别表示物品种数和背包容积。

接下来有 N 行，每行两个整数 vi,wi，用空格隔开，分别表示第 i 种物品的体积和价值。

输出格式：
输出一个整数，表示最大价值。

数据范围：
0<N,V≤1000
0<vi,wi≤1000

输入样例
4 5
1 2
2 4
3 4
4 5
输出样例：
10

-题解：

1.二维数组:

import java.util.Scanner;
public class Main{
public static void main(String[] args){
    Scanner sc=new Scanner(System.in);
    //读取物品得数量和背包得体积
    int N=sc.nextInt();
    int V=sc.nextInt();
    
    // 分别用于存储物品的体积和价值，数组下标从1开始使用，方便对应物品编号
    int[] v=new int[N+1];
    int[] w=new int[N+1];
    for(int i=1;i<=N;i++){
        v[i]=sc.nextInt();
        w[i]=sc.nextInt();
    }
    //定义一个二维dp数组，通过两层循环来填充dp数组，dp[i][j]表示在前i个物品中，背包容量为j时能获得的最大价值
    int[][] dp = new int[N + 1][V + 1];

    // 初始化边界情况，当没有物品可选（i = 0）时，无论背包容量是多少，最大价值都为0
    for (int j = 0; j <= V; j++) {
        dp[0][j] = 0;
    }
    //核心代码：
    for(int i=1;i<=N;i++){
        for(int j=0;j<=V;j++){
            //如果装得下
            if(j>=v[i]){
                dp[i][j]=Math.max(dp[i][j-v[i]]+w[i],dp[i-1][j]);
            }else{
                dp[i][j]=dp[i-1][j];
            }
        }
    }
    System.out.println(dp[N][V]);
}
}

总结：

题目：

• 有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。第 i 件物品的体积是 vi，价值是 wi。

求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
输出最大价值。

输入格式
第一行两个整数，N，V，用空格隔开，分别表示物品数量和背包容积。

接下来有 N 行，每行两个整数 vi,wi，用空格隔开，分别表示第 i 件物品的体积和价值。

输出格式
输出一个整数，表示最大价值。

数据范围
0<N,V≤1000

0<vi,wi≤1000

输入样例
4 5
1 2
2 4
3 4
4 5
输出样例：
8

• 看会了，就来试一试吧：经典的01背包问题
• 哈哈哈，祝你的代码状态为：Accepted
• 要是还不会就看看这几个大佬的视频讲解吧：黑马程序员(多看几遍，多动动手)、代码随想录中的算法公开课。
• 文字版的讲解：代码随想录
• 题解：创建了二维数组 dp，其中 dp[i][j] 表示在前 i 个物品中，当背包容量为 j 时所能获得的最大价值，通过这样使用二维数组的动态规划方法，全面地考虑了放入和不放入每个物品的各种情况，最终准确地求出满足条件的背包能够装入物品的最大总价值。
• 代码：

二维数组dp数组

import java.util.Scanner;
public class Main {
public static void main(String[] args) {
    Scanner scanner = new Scanner(System.in);
    // 读取物品数量N和背包容积V
    int N = scanner.nextInt();
    int V = scanner.nextInt();

    // 分别用于存储物品的体积和价值，数组下标从1开始使用，方便对应物品编号
    int[] v = new int[N + 1];
    int[] w = new int[N + 1];
    for (int i = 1; i <= N; i++) {
        v[i] = scanner.nextInt();
        w[i] = scanner.nextInt();
    }

    // dp[i][j]表示在前i个物品中，背包容量为j时能获得的最大价值
    int[][] dp = new int[N + 1][V + 1];

    // 初始化边界情况，当没有物品可选（i = 0）时，无论背包容量是多少，最大价值都为0
    for (int j = 0; j <= V; j++) {
        dp[0][j] = 0;
    }

    // 动态规划核心逻辑，通过两层循环来填充dp数组
    for (int i = 1; i <= N; i++) {
        for (int j = 0; j <= V; j++) {
            if (j >= v[i]) {
                // 如果背包容量j大于等于第i个物品的体积v[i]，可以选择放或不放该物品
                // 取放与不放该物品能得到的最大价值
                dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - v[i]] + w[i]);
            } else {
                // 如果背包容量j小于第i个物品的体积v[i]，无法放入该物品，价值与前i - 1个物品时相同
                dp[i][j] = dp[i - 1][j];
            }
        }
    }

    // 输出在前N个物品中，背包容量为V时能获得的最大价值
    System.out.println(dp[N][V]);

}
}

一维数组：

import java.util.Scanner;
public class KnapsackProblemOneDArray {
public static void main(String[] args) {
    Scanner scanner = new Scanner(System.in);
    // 读取物品数量N和背包容积V
    int N = scanner.nextInt();
    int V = scanner.nextInt();

    // 分别用于存储物品的体积和价值
    int[] v = new int[N + 1];
    int[] w = new int[N + 1];
    for (int i = 1; i <= N; i++) {
        v[i] = scanner.nextInt();
        w[i] = scanner.nextInt();
    }

    // dp[j]表示背包容量为j时能获得的最大价值（使用一维数组进行优化）
    int[] dp = new int[V + 1];

    // 动态规划核心逻辑，通过两层嵌套循环来填充dp数组
    for (int i = 1; i <= N; i++) {
        // 注意这里要从V开始逆序遍历到v[i]，避免重复使用更新后的数据
        for (int j = V; j >= v[i]; j--) {
            dp[j] = Math.max(dp[j], dp[j - v[i]] + w[i]);
        }
    }

    // 输出背包容量为V时能获得的最大价值
    System.out.println(dp[V]);
 }
}

动态规划的理论基础

• 总结：动态五部曲
  1.确定dp数组（dp table）以及下标的含义
  2.确定递推公式
  3.dp数组如何初始化
  4.确定遍历顺序
  5.举例推导dp数组
  详细来源：代码随想录

不同路径I

1. 题目：

• 一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish” ）。问总共有多少条不同的路径?

2. 公开课：不同路径I
3. 思路:

-

代码如下：

class Solution {
public int uniquePaths(int m, int n) {
    //定义一个dp的二维数组
    int[][] dp=new int[m][n];
    //初始化dp[i][0]和dp[0][i]
    for(int i=0;i<m;i++){
        dp[i][0]=1;
    }
    for(int i=0;i<n;i++){
        dp[0][i]=1;
    }
    //深推递推公式
   
    for (int i = 1; i < m; i++) {
        for (int j = 1; j < n; j++) {
            dp[i][j] = dp[i-1][j]+dp[i][j-1];
        }
    }
     return dp[m-1][n-1];
    
}
}