c语言背包问题(多维背包问题编程)

1. 前言

本节是贪婪算法系列之一:背包问题。主要解释了什么是背包问题，如何使用贪婪算法求解，给出了背包问题的实现伪代码，并对其进行了分析。用java语言实现，通过背包问题帮助人们更好地理解贪婪算法的应用。

2. 什么是背包问题？

假设我们共有N件物品，每件物品I的值为vi，重量为wi，我们有一个容量为C的背包(可放置物品的最大重量不能超过C)。我们需要选择物品放入背包，使背包中所选物品的总价值最大，这里只能选择每件物品的一部分。这就是我们常说的背包问题。

背包问题是一个可以用贪婪算法解决的常见问题。接下来，我们来看看如何用贪心算法解决背包问题。

3. 贪心算法求解背包问题

首先，这里我们考虑背包的容量为30，并给出我们在这个问题中考虑的各类物品及其对应的重量和数值，如下:

第n (i)条

一个

2

三

四

五

W (i)

10

五

15

10

20

价值(一)

20

30

15

25

10

回顾一下我们在贪婪算法介绍中提到的，贪婪算法能解决的问题需要满足两个条件:最优子结构和贪婪选择。接下来我们具体看看背包问题中的最优子结构和贪婪选择是什么。

首先，如果一个问题的最优解包含其子问题的最优解，那么这个问题具有最优子结构的性质。问题的最优子结构性质是问题能否用贪婪算法求解的关键。对于背包问题，显然它满足最优子结构性质，因为一个容量为C的背包问题必然包含容量小于C的背包问题的最优解。

其次，我们需要考虑在背包问题中我们应该做出什么样的贪婪选择。显然，如果你想最大化最终价值，你必须最大化每单位重量所选物品的价值。所以背包问题的贪婪选择策略是:优先选择单位重量价值最大的物品，当这个物品完成后，继续选择其他价值最大的物品。

这里背包问题可以用贪心算法实现，因为背包选择放入的物品是可以拆分的，也就是不需要放入整件物品，而是可以选择放入部分物品。我们的背包选择问题是一个部分背包问题(只能选择物品的部分)，另一个对应的背包问题是0-1背包问题。这时候整件物品不能拆分，只能放进去或者不放进去。贪婪算法无法精确求解0-1背包问题。

背包问题求解详解:

这里我们根据优先级选择单位重量值最高的物品，所以第一步是计算每个物品的单位价值，如下:

单位值(1) = 20/10 = 2单位值(2) = 30/5 = 6单位值(3) = 15/15 = 1单位值(4) = 25/10 = 2.5单位值(5) = 10/20 = 0.5代码块12345所以我们有:

unitValue(2)>unitValue(4)>unitValue(1)>unitValue(3)>UnitValue(5)当背包容量考虑为30时，我们发现可以按照物品的单位价值进行摆放，直到背包容量满了或者物品用完。摆放过程如下:

项目类型

增加重量

背包使用容量

背包剩余容量

2

五

五

25

四

10

15

15

一个

10

25

五

三

五

30

0

根据以上步骤，我们简要分析了背包问题的求解过程。接下来，我们来看看如何用代码实现背包问题。

4.JAVA 代码实现

解释完求解背包问题的全过程，接下来，我们来看看如何用java代码求解背包问题。

导入Java . util . ArrayList；导入Java . util . collections；导入Java . util . list；公共背包{/* * * item内部类*/私有静态类item实现可比< Item & gt{ int类型；双倍重量；双值；双单位值；public Item(int type，double weight){ this . type = type；this.weight =重量；} public Item(int type，double weight，double value){ this . type = type；this.weight =重量；this.value = valuethis.unitValue =值/重量；} @ Override public int compare to(Item o){ return double . value of(o . unit value)。compare to(this . unit value)；} } public static void main(string[]args){//背包容量双倍容量= 30；//项类型初始化数组int[] itemType = {1，2，3，4，5 }；//项目权重初始化数组double [] itemweight = {10，5，15，10，30 }；//初始化数组double [] itemvalue = {20，30，15，25，10}的项值；//初始化项目列表< Item & gtitemList = new ArrayList & lt& gt();for(int I = 0；我& lt项目类型.长度；i++){ Item Item = new Item(Item type[I]，itemWeight[i]，Item value[I])；item list . add(item)；}//项目按单价集合降序排序. sort(item list)；//背包选择列表；selectItemList = new ArrayList & lt；& gt();double select capacity = 0；for(Item Item:Item list){ if((select capacity+Item . weight)& lt；= capacity){ select capacity = select capacity+item . weight；Item selectItem = new Item(Item . type，Item . weight)；selectitemlist . add(selectItem)；} else { Item selectItem = new Item(Item . type，capacity-select capacity)；selectitemlist . add(selectItem)；打破；} }//选择(item item:selectitemlist){ system . out . println(& # 34；选定的类型:& # 34；+item . type+& # 34；物品，重量为:& # 34；+item . weight)；}}}运行结果如下:

带类型的物品:2，重量:5.0，类型:4，重量:10.0，类型:1，重量:10.0，类型:3，重量:5.0。代码中的第10到31行定义了一个内部的物品类，用于存储物品的类型、重量、价值和单位重量的价值。代码的第35到42行对应背包问题的初始化，分别初始化背包容量、物品类型、物品重量和物品价值。从代码的第44行到第51行，根据项目内部类的格式将所有项目添加到数组中，并根据项目单位重量的值按降序排序。从代码的第53行到第66行，根据背包问题的贪婪选择法选择相应的物品，记录所选物品的种类和重量，放入所选物品列表中。代码的第69行和第71行输出相关的项目选择结果。

5. 小结

这一部分主要研究如何使用贪婪算法来处理背包问题。学习本节贪婪算法求解背包问题的过程，可以用自己的代码求解背包问题。学完这一课，我们通过背包问题的例子来介绍贪婪算法的实际应用，帮助大家更好的理解贪婪算法。