经典背包问题的探讨
一、背包问题的描述
背包问题可以有多种形式，下面将对其逐一进行描述：
（1）经典的0-1背包问题（无物品的价值）：
假设有一个能装入容量为C的背包和n件重量分别为w1,w2,,...,wn的物品，能否从n件物品中挑选若干件恰好装满背包,要求找出所有满足上述条件的解。
当C=10,各件物品重量为{1,8,4,3,5,2}时，可以找到下列4组解：(1,4,3,2)、(1,4,5)、(8,2)和(3,5,2)。
根据这个问题的一个变形是：
已知一个数为C，一个长度为n的无序的数组，分别是数w1,w2,...,wn，能否从这n个数中找到若干个数使其和等于数C,要求找出所有满足上述条件的解。
（2）经典的0-1背包问题（有物品的价值）：
给定n种物品和一个背包。物品i的重量是wi，其价值为vi，背包的容量为C。应该如何选择装入背包中的物品，使得装入背包中物品的总价值最大？
上面的两个问题都是0-1背包问题，因为隐含的信息是：对每种物品只有两种选择，即装入背包或者不装入背包。不能将物品装入多次，也不能只装入部分的物品。
（3）背包问题：与0-1背包问题类似，所不同的是在选择物品i装入背包时，可以选择物品i的一部分，而不一定要全部装入背包。
二、解决思路
对于问题（1），本文采用的是回溯思想，利用栈的“后进先出”的特性 ，首先将物品排成一列，然后顺序选取物品装入背包，假设已选取了前i件物品之后背包还没装满，
则继续选取第i+1件物品，若选该件物品的重量太大不能装入，则放弃而继续选取下一件，直至背包装满为止。但是如果在剩余物品中找不到合适的物品以填满背包，则说明
“刚刚”装入背包的那件物品“不合适”，应该将它取出，再继续从它之后的物品中选取，如此重复，直至求得满足要求的解，或者无解为止。因为回溯的规则也是“后进先出”，
所以采用栈这个数据结构。
对于问题（2），其实可以采用问题（1）的解法 ，因为要使价值最大化，肯定也是尽可能多的往背包里装物品。只是此时不要求装满背包，而是在过程中不断比较每种情况的
总价值，并找到总价值最大的选择方式。
对于问题（3），这种背包问题可以用贪心算法求解 ，先计算每种物品单位重量的价值vi/wi;然后根据贪心策略，将可能多得单位重量价值最高的物品装入背包；依次使用这种
策略，直至装满背包为止。
三、程序设计
问题（1）：
问题（2）：
问题（3）：
正文到此结束
热门推荐
相关文章
近期评论
-
文章和留言都翻到11页了 没有OOM
-
-
朋友，翻页到11页，及以后，会出现OOM，无法访问
-
-
搞个gitee的项目
-
-
版本号是多少，你可以下载哪个代码仓库，jdk选1.8 直接跑就行
-
-
-
Loading...
![[HBLOG]公众号](https://www.liuhaihua.cn/img/qrcode_gzh.jpg)
