❝动态规划之01背包问题微信公众号:程序员风离
个人博客 : 点我
CSDN: 点我
欢迎━(`∀´)ノ亻!关注公众号
❞
❝问题引出:
「一个背包最大容量为8 现有4个物品 每个物品各自有不同的容量和不同的价值 求在不超过背包最大容量的情况下最大物品价值」
如图所示
❞ 物品编号 物品所需容量(weight) 物品价值(value) 126 2310 3412 4515
设 f(k,w) k为背包最大存入物品数量 w 为背包最大容量
每一次存放物品都有两种情况
-
weight>8 (太重放不下) -
放不下就向下走 k-1 w因为没存放物品 保持不变 f(k,w) =f(k-1,w)
-
-
weight<=8 (能放下 然后选择是否存放 这里也有两种情况 ) -
如果选择放下 f(k,w) = f(k-1,w-weight) + (weight,value) weight对应的value -
如果选择不放下 f(k,w) = f(k-1,w) 继续向下走 例如当前是第三号物品 存放不下 就向下找 三号物品是否能放下 (放不下 value为0)
-
❝ ❞由上述方程可列出图表
❝由上述方程可代码实现(Java)❞ 背包容量 0 1 2 3 4 5 6 7 8 0000000000 1: w =2 v=6006666666 2: w=3 v=10006101016161616 3: w=4 v=12006101216182222 4: w=5 v=15006101216182225
public class Test {
public static void main(String[] args) {
int[][] f =new int[5][9]; // f[i][j]表示前i件物品,背包容量为j的最大价值
int[]w=new int[]{0,2,3,4,5}; //重量
int[]v=new int[]{0,6,10,12,15}; //价值
for(int i=1;i<5;i++)
{
for(int j=1;j<9;j++)
{
if(w[i]>j)
{
f[i][j]=f[i-1][j];
}else {
f[i][j]=Math.max(f[i-1][j],f[i-1][j-w[i]]+v[i]);
}
}
}
for (int i = 0; i < 5; i++) {
for (int j = 0; j < 9; j++) {
System.out.print(f[i][j]+" ");
}
System.out.println();
}
}
}
运行截图:
符合图表所示
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)