精华内容
下载资源
问答
  • 动态规划求解01背包问题

    千次阅读 2019-04-22 21:35:05
    近期事情多,且老师讲动态...判断一个问题是否能用动态规划求解,要看它是否能划分成合适的子问题,然后写出递推关系式。 动态规划得到的解一定是最优解。 01背包问题 (1)问题描述: 现有n件物品,每件都有...

    近期事情多,且老师讲动态规划讲得云里雾里。。于是又没有跟上进度,菜鸡终于要来填坑了。

    动态规划

    动态规划和分治法有些相像,都是把一个问题分成了很多子问题来求解,但是不同的是动态规划会记忆之前解决的子问题的结果,避免了重复计算。判断一个问题是否能用动态规划求解,要看它是否能划分成合适的子问题,然后写出递推关系式。

    动态规划得到的解一定是最优解。

    01背包问题
    (1)问题描述:
    现有n件物品,每件都有对应的重量(w)和价值(v),有一个给定容量(C)的背包,怎么样才能在背包里装入具有最大价值总和的东西?
    具体例子:
    在这里插入图片描述
    (2)问题分析:
    突然想到之前看数模书的时候提到的一种思路——引入0-1变量,化为整数规划问题。
    模型建立:已知n件物品的重量为W1~Wn ,价值为V1 ~Vn,用X1 ~Xn来表示是否选了这件物品放入背包,Xi为0或1。
    决策目标即为:MAX(V1X1+V2X2+…+VnXn)
    约束条件即为:(W1X1+W2X2+…+WnXn) ≦ C
    抖机灵用lingo求了下解。。
    在这里插入图片描述
    好了言归正传。。
    (3)寻找子问题和建立递推关系式
    这里采用自底向上的思路
    定义子问题:在前i个物品里面挑选总重量不大于W(W<=C)的物品,记最优值为M(i, W),则对于第i个物品来说就有两种情况:
    ①Wi>W,装不下了,则M(i, W)=M(i-1, W);
    ②Wi<=W,那么就要选择装不装,则M(i, W)=max{M(i-1, W) , M(i-1, W-Wi)+Vi}
    M(i-1, W-Wi)即为第i个物品装入之前的最优值,结果是装了第i个物品。
    接下来就是初始化的问题了,还是看源代码吧。
    (4)源代码:

    public class FindMax {	
    	public static void main(String[] args){
    		int capacity=11;
    		int item_num=5;
    		int[][] M = new int[item_num+1][capacity+1];
    		int[] w={0,1,2,5,6,7};
    		int[] v={0,1,6,18,22,28};
    		int i,j;
    		for(i=0;i<=capacity;i++){
    			M[0][i]=0;
    		}
    		for(j=0;j<=item_num;j++){
    			M[j][0]=0;
    		}
    		for(i=1;i<=item_num;i++){
    			for(j=1;j<=capacity;j++){
    				if(w[i]>j){
    					M[i][j]=M[i-1][j];
    				}
    				else{
    					M[i][j]=Math.max(M[i-1][j], M[i-1][j-w[i]]+v[i]);
    				}
    			}
    		}
    		for(i=0;i<=item_num;i++){
    			for(j=0;j<=capacity;j++){
    				System.out.print(M[i][j]+ "\t");
    			}
    			System.out.println("");
    		}
    	}
    }
    

    结果截图如下:
    在这里插入图片描述
    最优解为40,那么怎么知道是哪几件物品被选中了呢?我们要从表的右下角往回看,M(5, 11)=M(4, 11)=40且M(4,11)不等于M[3,11],说明选了4号物品;减去4号物品的重量40-22=18,M(3, 5)=18且M(3,5)不等于M(2, 5)且M(3,5)=M(4,5)=M(5,5),说明第三件物品被选择了,减去三号物品的重量40-22-18=0;说明被选中的就是3号和4号。

    今天就写到这里吧。

    展开全文
  • 动态规划求解 01背包问题 java语言 1、求最优解及最优解路径 package G.C; import java.util.*; public class 动态规划01背包 { static int w[] = {0, 2,3,4,5 };//商品的体积2、3、4、5 static int v[] = {0,3,4,5,...

    动态规划求解 01背包问题 java语言

    1、求最优解及最优解路径
    package G.C;

    import java.util.*;

    public class 动态规划01背包 {

    static int w[] = {0, 2,3,4,5 };//商品的体积2、3、4、5
    static int v[] = {0,3,4,5,6 };//商品的价值3、4、5、6
    static int bagV = 8;	
    static int vBagv[][]= new int [5][9];
    static int maxV = 0 ;
    static Set<Integer> haveAdd = new HashSet<>();
    
    public static void main(String[] args) {
    	
    
    	for(int i=1;i<=4;i++){
    		for(int j=1;j<=8;j++){
    			if(j<w[i]){//不装入
    				vBagv[i][j] = vBagv[i-1][j];
    			}else{ //装入
    				vBagv[i][j] = Math.max( vBagv[i-1][j], vBagv[i-1][j-w[i]]+v[i]);
    			}
    			if(vBagv[i][j]>maxV){
    				maxV = vBagv[i][j];
    			}
    		}
    	}
    		
    	//求加入的商品体积
    	findAddLj(4,8);
    	
    	System.out.print(maxV);
    	System.out.print(haveAdd.toString());
    }
    
    private static void findAddLj(int i,int j) {
    	if(i>=1){
    		if(vBagv[i][j]  == vBagv[i-1][j] ){ //没加入 第 i个商品没加入
    			findAddLj(i-1,j);
    		}else{//
    			if(j>=w[i]&&vBagv[i][j]== vBagv[i-1][j-w[i]]+v[i] ){
    				haveAdd.add(w[i]);// 第 i个商品没加入
    				findAddLj(i-1,j-w[i]);
    			}
    		}
    	}
    	}
    

    }
    求解过程可参考 博客:
    https://blog.csdn.net/qq_38410730/article/details/81667885

    展开全文
  • 动态规划求解01背包问题 题目描述 给定N个物品,每个物品有一个重量W和一个价值V.你有一个能装M重量的背包.问怎么装使得所装价值最大.每个物品只有一个. 输入 输入的第一行包含两个整数n, m,分别表示物品的个数和...

    用动态规划求解01背包问题

    题目描述
    给定N个物品,每个物品有一个重量W和一个价值V.你有一个能装M重量的背包.问怎么装使得所装价值最大.每个物品只有一个.

    输入
    输入的第一行包含两个整数n, m,分别表示物品的个数和背包能装重量。
    以后N行每行两个数Wi和Vi,表示物品的重量和价值

    输出
    输出1行,包含一个整数,表示最大价值。

    样例输入
    3 5
    2 3
    3 5
    4 7

    样例输出
    8

    这里使用二维数组解决,会更加通俗易懂的。
    其实可以使用一维数组进行空间优化。

    package oj;
    import java.util.Scanner;
    
    /**
     * @author JMChen
     * @date 2020/4/24
     */
    public class ZeroOneBackpack {
        public static void main(String[] args) {
            Scanner sc = new Scanner(System.in);
            int num, weight;
    
            //求的是dp[num][weight]
            num = sc.nextInt();
            weight = sc.nextInt();
    
            int i, j;
    
    		//假设第一个为0,方便下标计算
            int[] p = new int[num + 1];
            int[] w = new int[num + 1];
            int[][] table = new int[num + 1][weight + 1];
    
    
            // 默认下标为0的取值为0,方便计算
            for (i = 1; i <= num; i++) {
                w[i] = sc.nextInt();            //每个东西的重量
                p[i] = sc.nextInt();            //每个东西的价值
            }
    
            //看成对d[i][j]的赋值
            //dp转移方程从d[1][1] 推出dp[num][weight]的值
            for (i = 1; i <= num; i++)
                for (j = 1; j <= weight; j++) {
                    if (j < w[i]) table[i][j] = table[i - 1][j];
                    else table[i][j] = Math.max(table[i - 1][j], table[i - 1][js - w[i]] + p[i]);
                }
    //可以将整个表打出来看看
    //        for(i=0;i<=num;i++)
    //        {
    //            for(j=0;j<=weight;j++)
    //                System.out.print(table[i][j]+ "  ");
    //            System.out.println();
    //        }
    
            System.out.print(table[num][weight]);
        }
    }
    
    

    关键思路:转移方程
    dp[i][j] = max(dp[i−1,j], dp[i−1][j−w[i]] + v[i])

    展开全文
  • 01背包问题:给定N中物品和一个背包,物品i的重量是Wi,其价值位Vi,背包的容量为C。问应该如何选择装入背包的物品,使得转入背包的物品的总价值为最大?每件物品可以选择装或者不装。 i代表前i个物品(包括i),j...

    01背包问题:给定N中物品和一个背包,物品i的重量是Wi,其价值位Vi,背包的容量为C。问应该如何选择装入背包的物品,使得转入背包的物品的总价值为最大?每件物品可以选择装或者不装。

    i代表前i个物品(包括i),j表示背包重量,f(i, j)表示从前i个物品中选取到总重量不超过j的最大价值。

    如果wi > j: f(i, j) = f(i-1, j) 否则f(i, j) = max(f(i-1, j), f(i-1, j-wi) +vi)。

    假设山洞里共有a,b,c,d ,e这5件宝物(不是5种宝物),它们的重量分别是2,2,6,5,4,它们的价值分别是6,3,5,4,6,现在给你个承重为10的背包, 怎么装背包,可以才能带走最多的财富。

    def package_max_value(weight, value, package_volume):
        if len(weight) <= 0 or len(value) <= 0 or len(weight) != len(value):
            return []
        res = [[0 for i in range(package_volume)] for i in range(len(value))]
        for j in range(package_volume):
            if j < weight[0]:
                res[0][j] = 0
            else:
                res[0][j] = value[0]
    
        for i in range(1, len(value)):
            for j in range(package_volume):
                if j < weight[i]:
                    res[i][j] = res[i-1][j]
                else:
                    res[i][j] = max(res[i-1][j], res[i-1][j-weight[i]] + value[i]) 
    
        return res
    
    weight = [2,2,6,5,4]
    value = [6,3,5,4,6]
    package_volume = 10
    print(package_max_value(weight, value, package_volume))
    运行结果如下。



    其中遇到二维数组赋值问题,res = [[0]* package_volume]*len(value),其中package_volume = 10, len(value)  = 5,生成二维数组后赋值操作,譬如res[1][2] = 20,结果每行的第三个元素变为20。原来是python中[array]*num中是创建了num个指向[array]的引用,一旦[array]改变,每行都改变。

    正确创建二维数组的方式是[[0 for i in range(row)] for j in range(column)]

    备注:一维数组通过[0]*5创建,是确实创建了5个元素,改变其中一个不影响其他元素。这么看来,*的操作是单个元素进行申请内容,而对list元素只做引用,只能deepcopy才可以真正复制list中的list元素。


    最长递增子序列:最长递增子序列(Longest Increasing Subsequence)是指找到一个给定序列的最长子序列的长度,使得子序列中的所有元素单调递增。
    例如:[3,5,7,1,2,8,4]的LIS是[3,5,7,8],长度为 4。

    def longest_ascending_sub(src):
        if len(src) <= 1:
            return src
        res = [1 for i in range(len(src))]
        subsequence = [[ele] for ele in src]
        for i in range(len(src)):
            for j in range(i):
                if src[i] >= src[j] and res[j] + 1 > res[i]:
                    res[i] = res[j] + 1
                    subsequence[i] = subsequence[j] + [src[i]]
        
        return res, subsequence
    
    src = [3,5,7,1,2,8,4]
    a, b = longest_ascending_sub(src)
    print('---每个位置最长递增序列的长度----')
    print(a)
    print('---每个位置最长递增序列的元素----')
    print(b)
    print('---最长数据为---\n%s'%len(b[a.index(max(a))]))
    运行结果如下。


    展开全文
  • 网址链接 http://exercise.acmcoder.com/online/online_judge_ques?ques_id=3812&amp;konwledgeId=41 ... 思路 ...之前想的是如果使用背包问题求解,则问题的空间复杂度很大,这个只包含1和2两...
  • 理论部分来自 ... 一、基本概念 ...一个决策序列就是在变化的状态中产生出来的,所以,这种多阶段最优化决策解决问题的过程就称为动态规划。 二、基本思想与策略  基本思想与分治法类似,也是将待求
  • 动态规划求解01背包问题 以下代码为动态规划求解01背包问题并统计代码运行300遍的平均运行时间。 #include <iostream> #include <windows.h> #include <iomanip> #include <time.h> ...
  • 使用动态规划求解01背包问题的程序,使用C语言编写。
  • 文章目录01背包问题动态规划01背包问题的动态规划求解01背包问题的动态规划求解-C++实现 01背包问题 有nnn个物品,这些物品的重量分别为w1,w2,...,wnw_1,w_2,...,w_nw1​,w2​,...,wn​,价值分别为v1,v2,...,vnv_1,...
  • 背包问题是经典问题,网上已经提供了很多优秀的解法,这里摘录动态规则的方法,同时顺便把背包相关的变形问题也一些阐述。 问题: 1. 经典背包问题:给定一个载重量为m,n个物品,其重量为wi,价值为vi,1 ...
  • 背包问题动态规划最具有代表性的问题。问题是这样的:问题法外狂徒张三是一个探险家,有一次巧合之下进入到一个有宝藏的洞穴里。这个洞穴有很多个不重复的宝贝,同时每个宝贝的重量也不一样。具体来说有:A 重 2 ...
  • 本文主要介绍动态规划算法求解01背包问题。什么是01背包问题?什么是动态规划动态规划怎么求解01背包问题?通过阅读本文能够解答上面的三个问题。 1、什么是01背包问题? 01背包问题是一种比较常见的问题,例如,...
  • 1.问题描述 问题描述参鉴...2.求解 package com.chb.DP; public class Pack01 { int[]value;//物品价值 int[]weight;//物品重量 int c;//背包容量 int[][]m; int[]x;//放入为1,不...
  • 对一个实际的背包问题,分别采用动态规划法和回溯法,以动态图ppt的形式生动形象地展示这两种算法的原理和求解过程
  • 有2种解题思路:动态规划法和穷举法。 1.穷举法 此方法需配合剪技算法,不然时间复杂度为2的n次方,此处略。 2.动态规划法 csdn中关于此方法的思路讲的非常多,此处略,例如: https://blog.csdn.ne...
  • [python] 动态规划求解背包问题

    千次阅读 2018-08-12 18:06:43
    动态规划求解01背包   01背包问题描述: 01背包问题可以假设为现在有一堆物品,每一个物品都具有两个属性,物品的重量和价值。现在有一个承重有限的背包,给定背包的最大承受重量。现在要将物品装入背包,使得...
  • 动态规划 01 背包问题 关键代码 for (int i = 1; i <= n; ++i) { for (int j = 0; j <= c; ++j) { if (j < w[i]) //如果背包剩余重量小于物品重量则该物品放不下 M[i][j] = M[i - 1][j]...
  • 01背包问题:递归、动态规划求解 //使用记忆化搜索:(存在重叠子问题:对于index,c这一数据对可能求解多次) int[][] memo; /** * 用[0...index]的物品,填充容积为c的背包的最大价值 * @param w:物体的重量 * ...
  • 动态规划——01背包问题 1.动态规划的基本思想 动态规划算法通常用于求解具有某种最优性质的问题。其基本思想也是将待求解问题分解成若干个子问题,先求解子问题,然后从这些子问题的解得到原问题的解。与分治法不同...
  • 动态规划(01背包问题)

    2020-09-02 16:01:00
    动态规划(01背包问题) 动态规划算法介绍 1) 动态规划(Dynamic Programming)算法的核心思想是:将大问题划分为小问题进行解决,从而一步步获取最优解的处理算法 2) 动态规划算法与分治算法类似,其基本思想也是将待...
  • 采用动态规划求解背包问题

    千次阅读 2018-05-03 14:08:04
    01背包问题,是用来介绍动态规划算法最经典的例子,这篇文章力争做到用最简单的方式,最少的公式把01背包问题讲解透彻。01背包的状态转换方程 f[i,j] = Max{ f[i-1,j-Wi]+Pi, f[i-1,j] } ( j &gt;= Wi )f[i,j]...
  • 问题 f: 0-1 背包问题动态规划) 时间限制:1 Sec内存限制:128 MB 提交:48解决:17 题目描述 给定n种物品和一个背包,物品i的重量是Wi,其价值为Vi,问如何选择装入背包的物品,使得装入背包的物品的总价值最大?...
  • 01背包问题动态规划求解

    千次阅读 2018-10-22 10:56:19
    这两天c++的习题开始不考察c++了,开始考察动态规划问题,唉,没学过动态规划算法来编这题目真是一把辛酸泪,下面给出题目(题目来源:郭玮老师的mooc) 2:Charm Bracelet 查看 提交 统计 提问 总时间限制: 1000ms ...
  • 01背包问题属于经典的动态规划问题,场景描述如下:形象描述:贼,夜入豪宅,可偷之物甚多,而负重能力有限,偷哪些才更加不枉此行?进一步抽象的话,就是:给定个物品,每种物品都有自己的重量和价值,在限定的总...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 571
精华内容 228
关键字:

动态规划求解01背包问题