算法系列--动态规划--背包问题(1)--01背包介绍(下)

简介: 算法系列--动态规划--背包问题(1)--01背包介绍(下)

算法系列--动态规划--背包问题(1)--01背包介绍(上)

https://developer.aliyun.com/article/1480834?spm=a2c6h.13148508.setting.14.5f4e4f0eIqvzeb

💕"趁着年轻,做一些比较cool的事情"💕

作者:Lvzi

文章主要内容:算法系列–动态规划–背包问题(1)–01背包介绍

大家好,今天为大家带来的是算法系列--动态规划--背包问题(1)--01背包介绍

状态转移方程

这里多了个限制条件dp[i - 1][j - v[i]] != -1,还是根据题目要求得来的,要考虑一种特殊情况,也就是在[0,i]区间内的物品根本无法组合成体积为j的情况(这也是会存在的),要想i位置存在价值,必须保证i-1位置刚好能够实现j-v[i]的体积

初始化相较于第一问也有所不同,具体来说需要把dp表的第一行初始化为-1(除了dp[0][0]),第一行代表不选择任何物品,也就无法构成满足j体积这个条件,我们将其设置为-1

之所以设置为-1是为了和dp[0][0] = 0这种情况作区分

代码:

import java.util.Scanner;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    static int N = 1010;
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt(), V = in.nextInt();// 获取物品数目和背包体积
        // 处理第一问
        int[] v = new int[N],w = new int[N];// 存储物品的体积和价值
        for(int i = 1; i <= n; i++) {// 输入数值
            v[i] = in.nextInt(); 
            w[i] = in.nextInt();
        }
        int[][] dp = new int[N][N];
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= V; j++) {
                dp[i][j] = dp[i - 1][j];
                if(j - v[i] >= 0) 
                    dp[i][j] = Math.max(dp[i - 1][j],dp[i - 1][j - v[i]] + w[i]);
            }
        }
        System.out.println(dp[n][V]);
        // 处理第二问
        dp = new int[N][N];
        for(int j = 1; j <= V; j++) {// 初始化
            dp[0][j] = -1;
        }
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= V; j++) {
                dp[i][j] = dp[i - 1][j];
                if(j - v[i] >= 0 && dp[i - 1][j - v[i]] != -1)
                    dp[i][j] = Math.max(dp[i - 1][j],dp[i - 1][j - v[i]] + w[i]);
            }
        }
        System.out.println(dp[n][V] == -1 ? 0 : dp[n][V]);
    }
}

上述解法的空间复杂度是很高的,我们开辟的dp表是一个N*N的,下面介绍使用滚动数组实现空间优化

空间优化之后的代码:

import java.util.Scanner;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    static int N = 1010;
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt(), V = in.nextInt();// 获取物品数目和背包体积
        // 处理第一问
        int[] v = new int[N],w = new int[N];// 存储物品的体积和价值
        for(int i = 1; i <= n; i++) {// 输入数值
            v[i] = in.nextInt(); 
            w[i] = in.nextInt();
        }
        int[] dp = new int[N];
        for(int i = 1; i <= n; i++) 
            for(int j = V; j >= v[i]; j--) 
                dp[j] = Math.max(dp[j],dp[j - v[i]] + w[i]);
            
        System.out.println(dp[V]);
        // 处理第二问
        dp = new int[N];
        for(int j = 1; j <= V; j++) 
            dp[j] = -1;// 初始化
        for(int i = 1; i <= n; i++) 
            for(int j = V; j >= v[i]; j--) 
                if(j - v[i] >= 0 && dp[j - v[i]] != -1)
                    dp[j] = Math.max(dp[j],dp[j - v[i]] + w[i]);
              
        System.out.println(dp[V] == -1 ? 0 : dp[V]);
    }
}

总结:本文的核心要点

  1. 什么是背包问题
  2. 01背包问题详解
  3. 背包问题的空间优化(滚动数组)

以上就是算法系列--动态规划--背包问题(1)--01背包介绍全部内容,下一篇文章将会带来01背包问题的拓展题目,敬请期待,我是LvZi


目录
相关文章
|
21天前
|
机器学习/深度学习 存储 算法
动态规划算法深度解析:0-1背包问题
0-1背包问题是经典的组合优化问题,目标是在给定物品重量和价值及背包容量限制下,选取物品使得总价值最大化且每个物品仅能被选一次。该问题通常采用动态规划方法解决,通过构建二维状态表dp[i][j]记录前i个物品在容量j时的最大价值,利用状态转移方程避免重复计算子问题,从而高效求解最优解。
244 1
|
21天前
|
算法 搜索推荐 Java
贪心算法:部分背包问题深度解析
该Java代码基于贪心算法求解分数背包问题,通过按单位价值降序排序,优先装入高价值物品,并支持部分装入。核心包括冒泡排序优化、分阶段装入策略及精度控制,体现贪心选择性质,适用于可分割资源的最优化场景。
148 1
贪心算法:部分背包问题深度解析
|
8月前
|
存储 算法 Java
算法系列之动态规划
动态规划(Dynamic Programming,简称DP)是一种用于解决复杂问题的算法设计技术。它通过将问题分解为更小的子问题,并存储这些子问题的解来避免重复计算,从而提高算法的效率。
269 4
算法系列之动态规划
|
8月前
|
算法 安全 调度
【动态规划篇】穿越算法迷雾:约瑟夫环问题的奇幻密码
【动态规划篇】穿越算法迷雾:约瑟夫环问题的奇幻密码
|
8月前
|
机器学习/深度学习 算法 测试技术
【动态规划篇】01 背包的逆袭:如何用算法装满你的 “财富背包”
【动态规划篇】01 背包的逆袭:如何用算法装满你的 “财富背包”
|
13天前
|
存储 编解码 算法
【多光谱滤波器阵列设计的最优球体填充】使用MSFA设计方法进行各种重建算法时,图像质量可以提高至多2 dB,并在光谱相似性方面实现了显著提升(Matlab代码实现)
【多光谱滤波器阵列设计的最优球体填充】使用MSFA设计方法进行各种重建算法时,图像质量可以提高至多2 dB,并在光谱相似性方面实现了显著提升(Matlab代码实现)
|
15天前
|
传感器 机器学习/深度学习 算法
【使用 DSP 滤波器加速速度和位移】使用信号处理算法过滤加速度数据并将其转换为速度和位移研究(Matlab代码实现)
【使用 DSP 滤波器加速速度和位移】使用信号处理算法过滤加速度数据并将其转换为速度和位移研究(Matlab代码实现)
103 1
|
14天前
|
传感器 机器学习/深度学习 算法
【UASNs、AUV】无人机自主水下传感网络中遗传算法的路径规划问题研究(Matlab代码实现)
【UASNs、AUV】无人机自主水下传感网络中遗传算法的路径规划问题研究(Matlab代码实现)
|
13天前
|
机器学习/深度学习 传感器 算法
【高创新】基于优化的自适应差分导纳算法的改进最大功率点跟踪研究(Matlab代码实现)
【高创新】基于优化的自适应差分导纳算法的改进最大功率点跟踪研究(Matlab代码实现)
111 14
|
13天前
|
机器学习/深度学习 运维 算法
【微电网多目标优化调度】多目标学习者行为优化算法MOLPB求解微电网多目标优化调度研究(Matlab代码实现)
【微电网多目标优化调度】多目标学习者行为优化算法MOLPB求解微电网多目标优化调度研究(Matlab代码实现)

热门文章

最新文章