背包问题(贪婪算法)

贪婪算法思想

简单来说，就是把一个大问题转化为一个更优子问题。例如，根据本主题的要求，背包的容量是有限的。如果我们想更大化物品的总价值，我们必须尽可能选择重量更高(即单位价值更高)的物品进行装载。

在背包问题中，物品是可拆卸的，即可以分成任意部分进行装载，最终目标是背包装满(即剩余容量为0)，总值尽可能高。这就是背包问题和0-1背包的根本区别。

问题解决思维

首先，对所有项目的权重进行排序(可以使用任何排序方法)

从更大重量的那个装载(如果合适的话)

重量较大的装载成功后，包装的更大剩余容量也会改变，即减去前一个项目的容量

继续重复2和3操作

直到更大剩余能力小于当前物料的重量，物料才会被分解为当前更大剩余能力

计算每个零件的总值和装载重量

代码如下：

公共静态无效bG(Bag[] p，int k，int w，double v)

{

for(int I=k；i p.lengthI){ 0

if(p[i]。重量=w)

{

v=v p[i]。价值；

System.out.println(p[i])。pid '全部加载，当前背包值为' v '；

w=w-p[i]。重量；

}else{

double a=w*p[i]。作业指导书；//当前值

v=v a；

System.out.println(p[i])。pid '加载了'((双)w/p[i]。重量)'，当前背包值为' v '；

}

}

}

一个

2

三

四

五

六

七

八

九

10

11

12

13

14

15

16

完整的代码实现如下

导入Java . util . scanner；

班级包

{

公共整数权重；//重量

公共int值；//值

公共双wi；//重量

公共字符串pid//背包名称

公共包(整数，整数，字符串)

{

this . weight=w；

this . value=v；

this.pid=pid

this.wi=(双倍)值/重量；

}

}

公共类bagGreed

{

//选择排序以按重量对阵列中的袋子进行排序(使用选择排序)

公共静态空排序(Bag[] p)

{

袋子t；

for(int I=0；ip.length(一)

{

int max=I；

t=p[I]；

for(int j=I；jp.lengthj)

{

if(t.wip[j])。wi)

{

t=p[j]；

max=j；

}

}

t=p[I]；

p[I]=p[max]；

p[max]=t；

}

}

//算法核心

公共静态无效bG(Bag[] p，int k，int w，double v)

{

for(int I=k；i p.lengthI){ 0

if(p[i]。重量=w)

{

v=v p[i]。价值；

System.out.println(p[i])。pid '全部加载，当前背包值为' v '；

w=w-p[i]。重量；

}else{

double a=w*p[i]。作业指导书；//当前值

v=v a；

System.out.println(p[i])。pid '加载了'((双)w/p[i]。重量)'，当前背包值为' v '；

}

}

}

公共静态void main(String args[])

{

System.out.println('请输入背包容量w和物品数量n ')；

扫描仪阅读器=新扫描仪(system . in)；

int w=reader . nextint()；//背包容量

int n=reader . nextint()；//项目数

Bag[]p=new Bag[n]；

//10 10a 10 b 10 15 c

System.out.println('请依次输入每件物品的重量W、价值V和名称S ')；

国际重量；

int值；

字符串pid

for(int I=0；在；(一)

{

weighth=reader . nextint()；

value=reader . nextint()；

PID=reader . next()；

p[I]=新Bag(重量、值、PID)；

}

sort(p)；

System.out.println('每个项目的重量为：')；

for(int I=0；在；(一)

{

System.out.println(p[i])。我。PID)；

}

bG(p，0，w，0.0)；

}

}