题目：

• 有 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];
    
}
}

贪心算法的理论基础

• 总结：代码随想录

最大子序和

1. 给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

• 例如：对于数组 [ -2, 1, -3, 4, -1, 2, 1, -5, 4 ]
• 它能够找出和最大的连续子数组（子数组是数组中的一个连续部分。在这里是 [ 4, -1, 2, 1 ]，其和为 6）
• 并返回这个最大和的值。
• Leetcode题目链接

思路

2. 说实话一开始看到这个题目，脑子的反应就是想用暴力解法，结果一试一试，还真行。哈哈。

• 思路：暴力解法的思路，第一层 for 就是设置起始位置，第二层 for 循环遍历数组寻找最大值。

代码如下：

class Solution {
public int maxSubArray(int[] nums) {
    int result =Integer.MIN_VALUE;
    int count = 0;
    for (int i = 0; i < nums.length; i++) { // 设置起始位置
        count = 0;
        for (int j = i; j < nums.length; j++) { // 每次从起始位置i开始遍历寻找最大值
            count += nums[j];
            result = count > result ? count : result;
        }
    }
    return result;


}
}

• 但是时间复杂度：O(n^2)
• 空间复杂度：O(1)，不推荐，还有更好的算法

3. 那么就是贪心算法(其实也还有其他的解法，例如：dp动态规划)

代码：

class Solution {
public int maxSubArray(int[] nums) {
    if (nums.length == 1){
        return nums[0];
    }
    int sum = Integer.MIN_VALUE; //sum：用于记录在遍历数组过程中找到的最大子数组的和，
    //初始化为 Integer.MIN_VALUE（Java 中 int 类型能表示的最小值），这样可以确保后续在比较和更新最大和时，任何有效的子数组和都能够比初始值大，从而可以正确地更新 sum 的值。
    int count = 0; //count：用于累计当前正在考虑的连续子数组的元素和，初始化为 0，随着遍历数组不断累加元素的值来更新这个累计和
    for (int i = 0; i < nums.length; i++){
        count += nums[i];
        sum = Math.max(sum, count); // 取区间累计的最大值（相当于不断确定最大子序终止位置）
        if (count <= 0){
            count = 0; // 相当于重置最大子序起始位置，因为遇到负数一定是拉低总和
        }
    }
   return sum;
}
}