贪心算法——背包问题-创新互联

14天阅读挑战赛

成都创新互联企业建站,10年网站建设经验，专注于网站建设技术，精于网页设计，有多年建站和网站代运营经验，设计师为客户打造网络企业风格，提供周到的建站售前咨询和贴心的售后服务。对于成都网站制作、成都网站建设中不同领域进行深入了解和探索，创新互联在网站建设中充分了解客户行业的需求，以灵动的思维在网页中充分展现，通过对客户行业精准市场调研，为客户提供的解决方案。

1.题目描述

2.问题分析

3.算法设计

4.C++程序

5.算法复杂度及优化

5.1算法复杂度分析

5.2算法优化扩展

1.题目描述

有n种物品，每种物品只有一个，第i种物品的重量为 $w_{i}$ ，价值为 $v_{i}$ ，背包的容量为W，物品可以分割。如何放置物品，使得背包的物品价值大？

i个物品重量及其价值如下：

物品清单
物品i	1	2	3	4	5	6	7	8	9	10
重量 $w_{i}$	4	2	9	5	5	8	5	4	5	5
价值 $v_{i}$	3	8	18	6	8	20	5	6	7	15

2.问题分析

由于物品可以分割，贪心策略选择单位重量价值大的物品装入背包最为合适。所以在选择过程中需要将物品按照单位重量价值递减的顺序进行排序，以此取前面单位重量价值大的物品。

3.算法设计

1）将物品的重量、价值和单位重量价值定义为一种结构体类型，方便对其按照单位重量价值从大到小进行排序。

2）根据贪心算法策略，以此取单位重量价值的大物品存入背包中，直至背包填满，如果到达第i个物品时超出了背包容量，那么就取该物品其中的一部分放入背包中。

4.C++程序

#include#include
using namespace std;

struct item {
	double w;//物品重量
	double v;//物品价值
	double p;//物品单位重量价值(价值/重量)
};
bool cmp(item a, item b) {
	return a.p >b.p;
}
item s[1000];
int main() {
	int n;
	double sum = 0,w,wleft;
	wleft = w;
	cin >>w>>n;
	for (int i = 0; i< n; i++) {
		cin >>s[i].w >>s[i].v;
		s[i].p = s[i].v / s[i].w;
	}
	sort(s, s + n, cmp);
	for (int i = 0; i< n; i++) {
		if (s[i].w<= wleft) {
			wleft -= s[i].w;
			sum += s[i].v;
		}
		else {
			sum += wleft * s[i].p;
			break;
		}
	}
	system("pause");
	return 0;
}

5.算法复杂度及优化 5.1算法复杂度分析

（1）时间复杂度：程序运行时间主要耗费在对物品按照单位重量价值排序上，采用的C++头文件algorithm中的sort方法，此方法采用快速排序，时间复杂度为O( $n\log n$ )。

（2）空间复杂度：空间主要耗费在对物品的存储上。空间复杂度为O(定义数组的大小)。

5.2算法优化扩展

如果物品不可分割，那么使用该贪心算法是否可以得到最优解呢？

物品可分割的背包问题称为背包问题，物品不可分割的背包问题称为0/1背包问题。0/1背包问题已经不具备贪心选择的性质，并不能通过局部最优达到全局最优。

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧

当前标题：贪心算法——背包问题-创新互联
本文URL：http://ybzwz.com/article/igpoe.html

贪心算法——背包问题-创新互联

其他资讯