文/michaelgbw
要了解背包，首先得清楚动态规划：
动态规划算法可分解成从先到后的4个步骤：
- 描述一个最优解的结构；
- 递归地定义最优解的值；
- 以“自底向上”的方式计算最优解的值；
- 从已计算的信息中构建出最优解的路径。
背包问题就是一个固定容量的背包，然后有一些商品，本身有两个属性，一个体积和价值，人总是贪婪的，总想获得最多的价值。
其实背包问题有好多版本：
- 01背包（ZeroOnePack）: 有N件物品和一个容量为V的背包。每种物品均只有一件,第i件物品的费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使价值总和最大。
- 完全背包(CompletePack): 有N种物品和一个容量为V的背包，每种物品都有无限件可用。第i种物品的费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。
- 多重背包(MultiplePack): 有N种物品和一个容量为V的背包。第i种物品最多有n[i]件可用，每件费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。
比较三个题目，会发现不同点在于每种背包的数量，01背包是每种只有一件，完全背包是每种无限件，而多重背包是每种有限件。
此文值研究0-1背包问题，也就是最长见的背包问题。
01背包（ZeroOnePack）: 有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]} （这是最根本的算法）
代码
由于最近在面试，PHP，js都要会，所以这次的代码我用js来写~
//动态规划算法
//数组中去除重复的算法
Array.prototype.unique = function(){
this.sort();
var re=[this[0]];
for(var i = 1; i < this.length; i++)
{
if( this[i] !== re[re.length-1])
{
re.push(this[i]);
}
}
return re;
}
function max(a,b){
return (a > b) ? a: b;
}
function dynamicPack(capacity, size, value){
var arr=new Array();
var n=size.length;//item 的数量
var k = new Array();
//手动构建二维array
for(var i=0;i<= capacity+1;i++){
k[i]=[];
}
for(var i=0;i<=n;i++){
for(var w=0;w <= capacity;w++){
if(i==0 || w==0){
k[i][w]=0;//表示当物体为前面i个,背包容量为w的最大价值
}
else if(size[i-1] <= w){//大小为size[i-1]的物品可以放入背包时
k[i][w]=max(value[i-1] +k[i-1][w-size[i-1]] , k[i-1][w]);
if(k[i][w] !=k[i-1][w])
arr.push(value[i-1]);
}
else{//大小为size[i-1]的物品不能放入背包时
k[i][w]=k[i-1][w];
}
document.write(k[i][w]);
document.write("...");
}
document.write("<br>");
}
var unarr=arr.unique();
//console.log(unarr);
var tem=0;
var re=[];
//k[n][capacity]是总价
for(var i in unarr){
if(tem <= k[n][capacity]){
re.push(unarr[i]);
tem+= parseInt(unarr[i]);
}
}
//return re;//选取的商品价值
return k[n][capacity];//最大价值
}
var value = [6,5,10,11,13];//价值
var size = [3,4,7,8,9];//尺寸
var capacity = 16;//背包容量
var result=dynamicPack(capacity,size,value);
console.log(result);
为了方便大家查看内部究竟是怎样运作的，这里特地将每次的动态数组都document.write()出来了
可以看到基本的算法就是：两层循环，第一次的for是商品的个数，第二次for是背包的容量。然后k数组中的每次的数据k[i]的key其实是商品的尺寸，value是商品的价值，每次遇到新的商品就和之前的总价比较，看”有没有必要“放入。之后一旦接受了新的商品，就暂存入数组，之后倒叙序便可以获取到相应的商品值了。
这既是基本算法了，return我提供了两个一个是最大价，一个是最大价的每个商品的价值。这算是真正明白点了吧~
网友评论