背包问题学习笔记

xiao7cn 发布于2019-08-20 18:05 / 2409人阅读

摘要：状态转移方程背包问题的状态转移方程是其中即表示前件物品恰放入一个容量为的背包可以获得的最大价值。求解将哪些物品装入背包可使这些物品的体积总和不超过背包容量，且价值总和最大。

01背包 01背包的概念

有N件物品和一个容量为V的背包。第i件物品的费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使价值总和最大。
从这个题目中可以看出，01背包的特点就是：每种物品仅有一件，可以选择放或不放。

状态转移方程

01背包问题的状态转移方程是:

f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]}

其中,即fi表示前i件物品恰放入一个容量为v的背包可以获得的最大价值。
上述方程右边可以理解为两种情况,取最优值.
情况一:第i件不放进去,这时所得价值为:fi-1;
情况二:第i件放进去,这时所得价值为:fi-1]+w[i];

情况二的意思是,如果第i件放进去,那么在容量V-c[i]里就要放进前i-1件物品.(引用自)

案例解析

有编号分别为a,b,c,d,e的五件物品，它们的重量分别是2,2,6,5,4，它们的价值分别是6,3,5,4,6，现在给你个承重为10的背包，如何让背包里装入的物品具有最大的价值总和？

首先要明确这张表是至底向上，从左到右生成的.
只要你能通过找规律手工填写出上面这张表就算理解了01背包的动态规划算法。
为了叙述方便，用e2单元格表示e行2列的单元格，这个单元格的意义是用来表示只有物品e时，有个承重为2的背包，那么这个背包的最大价值是0，因为e物品的重量是4，背包装不了
对于d2单元格，表示只有物品e，d时,承重为2的背包,所能装入的最大价值，仍然是0，因为物品e,d都不是这个背包能装的。(引用自)

编程实现

var n = 5; //物品数量,该参数可以自行设定
var v = 10; //背包体积,该参数可自行设定
var volumArray = [4, 3, 5, 2, 5];//物品体积组成的数组,该参数可自行设定
var valueArray = [9, 6, 1, 4, 1];//物品价值组成的数组,该参数可自行设定
var tempArray = [];

for (let a = 0; a < n; a++) {
    tempArray[a] = [];
    for (let b = 0; b < v; b++) {
        tempArray[a].push(0);
    }
}

for (let i = 0; i < n; i++) {
    for (let j = 0; j < v; j++) {
        tempArray[i][j] = i == 0 ? 0 : tempArray[i - 1][j];
        if (i > 0 && j >= volumArray[i - 1]) {
            tempArray[i][j] = tempArray[i][j] >= tempArray[i - 1][j - volumArray[i - 1]] + valueArray[i - 1] ? tempArray[i][j] : tempArray[i - 1][j - volumArray[i - 1]] + valueArray[i - 1];
        }
    }
}

console.log(tempArray[n - 1][v - 1]);

完全背包 完全背包的概念

有N种物品和一个容量为V的背包，每种物品都有无限件可用。
第i种物品的体积是c，价值是w。求解将哪些物品装入背包可使这些物品的体积总和不超过背包容量，且价值总和最大。

状态转移方程

参考上述01背包的转移方程,不难得出:

f[i][v]=max{f[i-1][v-k*c[i]]+k*w[i]|0<=k*c[i]<=v}

伪代码实现如下:

for i=1...N
    for v=0...V
        for k=1...v/w[i]
            f[i][v] = max{f[i-1][v],f[i-1][v-k*w[i]]+k*c[i]};

案例解析

给你六种面额1,5,10,20,50,100元的纸币,假设每种币值的数量都足够多,编写程序求组成N元的不同组合个数.

function fn (all) {
    const arr = [1, 5, 10, 20, 50, 100],
        len = arr.length,
        res = [];
    for (let i = 0; i <= len; i++) {
        res[i] = [];
        res[i][0] = 1;
    }
    for (let j = 1; j <= all; j++) {
        res[0][j] = 0;
    }
    for (let i = 1; i <= len; i++) {
        for (let j = 1; j <= all; j++) {
            res[i][j] = 0;
            for (let k = 0; k <= j / arr[i - 1]; k++) {
                res[i][j] += res[i - 1][j - k * arr[i - 1]];
            }
        }
    }
    return res[len][all];
}

GPU云服务器云服务器背包问题 java背包凑钱问题学习笔记学习笔记一

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/84070.html

遗传算法解背包问题（javascript实现）

摘要：遗传算法物竞天择，适者生存，遗传算法就是借鉴生物体自然选择和自然遗传机制的随机搜索算法。随机生成的基因适应度的最大值随机生成，适应度函数计算种群中所有对象的适应度及总和，并对超出的基因进行惩罚。此为《算法的乐趣》读书笔记，我用javascript（ES6）重新实现算法。遗传算法物竞天择，适者生存，遗传算法就是借鉴生物体自然选择和自然遗传机制的随机搜索算法。算法的关键点有：基因的选...

longshengwang 2019-08-19 18:10 评论0 收藏0
算法学习笔记一、时空复杂度

摘要：动态规划背包士兵路径复杂度谈算法一定要考虑复杂度时间复杂度和空间复杂度时间复杂度计算机基本操作的次数汇编指令的条数寻址跳转空间复杂度所需占用的内存字节数两者区别空间是可以返回利用的。面试求职班一笔记算法主要研究：时空复杂度算法的特征：有穷性，确定性，可行性，可能没有输入，但一定有输出常用算法穷举法（eg：求N个数的全排列；8皇后问题）减而治之（二分查找...

wuyumin 2019-08-16 11:08 评论0 收藏0
数据结构与算法之精讲「递归系列」

摘要：终止条件递推公式递归的分类通过做大量的题，根据递归解决不同的问题，引申出来的几种解决和思考的方式。我们通过层与层之间的计算关系用递推公式表达出来做计算，经过层层的递归，最终得到结果值。 showImg(https://segmentfault.com/img/remote/1460000019222330); 前言几个月之前就想写这样一篇文章分享给大家，由于自己有心而力不足，没有把真...

zhichangterry 2019-08-26 13:50 评论0 收藏0
Python遗传算法框架DEAP-Creating Types

摘要：是一个遗传算法框架，这里是它的简介。最小化问题使用负值的的最大化问题用正值。略种群种群横线个体。这个种群是直接使用和函数来初始化的。个体之间分布在网格中每个格子包含一个个体。调用将会返回一个种群，个体是使用两个索引可获得的。 DEAP是一个python遗传算法框架，这里是它的简介。DEAP documentation今天整理一下DEAP的概览，大体了解一下它的流程。初学，不严谨，仅作为...

Channe 2019-07-24 18:25 评论0 收藏0