题目
有N件物品和一个容量为V的背包。第i件物品的费用是c[i],价值是w[i]。求解将哪些物品装入背包可使价值总和最大。
基本思路
这是最基础的背包问题,特点是:每种物品仅有一件,可以选择放或不放。
用子问题定义状态:即f[i][v]表示前i件物品恰放入一个容量为v的背包可以获得的最大价值。
状态转移方程:
f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]}
这个方程非常重要,基本上所有跟背包相关的问题的方程都是由它衍生出来的。
所以有必要将它详细解释一下:“将前i件物品放入容量为v的背包中”这个子问题,若只考虑第i件物品的策略(放或不放),那么就可以转化为一个只牵扯前i-1件物品的问题。
- 如果不放第i件物品,那么问题就转化为“前i-1件物品放入容量为v的背包中”,价值为f[i-1][v];
- 如果放第i件物品,那么问题就转化为“前i-1件物品放入剩下的容量为v-c[i]的背包中”,此时能获得的最大价值就是f[i-1][v-c[i]]再加上通过放入第i件物品获得的价值w[i]。
<script type="text/javascript">
$(function () {
$('pre.prettyprint code').each(function () {
var lines = $(this).text().split('\n').length;
var $numbering = $('<ul/>').addClass('pre-numbering').hide();
$(this).addClass('has-numbering').parent().append($numbering);
for (i = 1; i <= lines; i++) {
$numbering.append($('<li/>').text(i));
};
$numbering.fadeIn(1700);
});
});
</script>
分享到:
相关推荐
01背包问题属于组合优化问题的一个例子,求解01背包问题的过程可以被视作在很多可行解当中求解一个最优解。01背包问题的一般描述如下: 给定n个物品和一个背包,物品i的重量为Wi,其价值为Vi,背包的容量为C。选择...
算法效果较为良好,实现背包问题价值最大,采用遗传算法实现的比较不错的结果
实验目的:0/1背包问题的回溯算法设计 实验原理:回溯算法设计。 实验要求:基本掌握回溯算法设计的原理方法。熟练掌握VC++中编程实现算法的常用技术和方法。 算法思想: 0-1背包问题:给定n种物品和一背包.物品i的...
使用遗传算法解决0-1背包问题,调试成功,非常适合初学者了解遗传算法和0-1背包问题
贪心算法 背包问题 c语言 绝对无误 运行成功
贪心算法解背包问题,供读者参考,我想看看有没有动态规划算法的解决办法
【背包问题】基于PSO算法求解01背包问题
关于背包问题的源代码,包括贪心算法和动态算法
经典遗传算法(SGA)解01背包问题的python代码实现,说明如下: 1.采用经典的二进制编码,选择算子为轮盘赌选择,交叉算子为两点交叉,变异算子为反转(单点)变异 2.可调的参数为:gen,pc,pm,popsize,n,w,c,W,M 3.两...
01背包问题的贪心算法,详细解析,令你很快懂的01背包问题中的贪心算法思想
用禁忌搜索算法求解背包问题。假设背包容量一定,已知每种物品的体积和价值,求出使价值最大的最优解。
简单的遗传算法用于解决背包问题codeblocks编写,运行成功
用贪心算法实现背包问题 集SSH框架,android,行业资讯,数据库,web开发,设计模式希望大家一起分享
算法设计与分析实验1: 用C语言,采用遗传算法来求解01背包问题。报告及其源代码(源代码附在报告最后面。)
01背包问题属于组合优化问题的一个例子,求解01背包问题的过程可以被视作在很多可行解当中求解一个最优解。01背包问题的一般描述如下: 给定n个物品和一个背包,物品i的重量为Wi,其价值为Vi,背包的容量为C。选择...
背包 背包问题 背包算法 背包 noip 竞赛 信息技术 基础算法
利用回溯算法解决0/1背包问题。类knapsack为背包类,bound是上界函数,函数bknapsack实现0/1背包回溯算法。内有详细注释。
背包问题.本算法比较清晰,易读。...背包问题是比较经典的算法。很具有代表性。在对问题求解时,总是做出在当前看来是最好的选择。也就是说,不从整体最优上加以考虑,他所做出的仅是在某种意义上的局部最优解。
本程序使用遗传算法来解决背包问题,0-1背包问题,使用C语言编写,带测试数据
01背包问题属于组合优化问题的一个例子,求解01背包问题的过程可以被视作在很多可行解当中求解一个最优解。01背包问题的一般描述如下: 给定n个物品和一个背包,物品i的重量为Wi,其价值为Vi,背包的容量为C。选择...