【贪心策略】背包问题——阿里巴巴与四十大盗

叁歲伎倆 2022-09-10 11:25 106阅读 0赞

## 一、问题 ##

假设山洞中有N种宝物，每种宝物有一定的重量w和相应的价值v，大盗的运载能力有限，只能随身携带重量M的宝物，一种宝物只能拿一样，宝物可以分割。那么怎么才能一次带走宝物的价值最大呢？

## 二、分析 ##

根据题意，无外乎有以下三种策略：

1.  每次挑选价值最大的宝物装入背包
2.  每次挑选重量最小的宝物装入背包
3.  每次选取单位重量价值最大的宝物装入背包

根据贪心策略，为了同时满足重量限制和价值最大化，我们应该采用策略3。

## 三、解法 ##

c++实现方法如下：

#include<iostream>
    #include<algorithm>
    
    using namespace std;
    const int MAX_NUM=1000;
    
    struct three { 
    	double w; //重量
    	double v; //宝物价值
    	double p; //性价比
    }s[MAX_NUM];
    
    bool cmp(three a, three b) { 
    	return a.p > b.p;  //根据宝物单价降序排序
    }
    
    int main() { 
    	int N; //表示有n个宝物
    	double M; //表示最大承载能力
    	cin >> N >> M;
    	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);
    	double sum = 0.0;
    	for (int i = 0; i < N; i++) { 
    		if (s[i].w < M) {   //如果装得下
    			M -= s[i].w;
    			sum += s[i].v;
    		}
    		else{   //如果装不下,就装部分
    			sum += M * s[i].p;
    			break;
    		}		
    	}
    	cout << "装入的最大价值为："<<sum<<endl;
    	return 0;
    }

## 四、进阶 ##

**如果假设每种宝物最多可以拿2个，且不能分割，必须按整个拿**，那么怎么才能一次带走宝物的价值最大呢？

C++实现如下：

#include<iostream>
    #include<algorithm>
    
    using namespace std;
    const int MAX_NUM=1000;
    
    struct three { 
    	double w; //重量
    	double v; //能量值
    	double p; //性价比
    }s[MAX_NUM];
    
    bool cmp(three a, three b) { 
    	return a.p > b.p;  //根据宝物单价降序排序
    }
    
    int main() { 
    	int N; //表示有n个宝物
    	double M; //表示最大承载能力
    	cin >> N >> M;
    	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);
    	double sum = 0.0;
    	for (int i = 0; i < N; i++) { 
    		if (2 * s[i].w <= M) {   //如果装得下2个
    			M -= 2 * s[i].w;
    			sum += 2 * s[i].v;
    		}
    		else if (s[i].w < M) {  //如果只装得下1个
    			M -= s[i].w;
    			sum += s[i].v;
    		}
    		else{   //如果装不下
    			break;
    		}		
    	}
    	cout << "装入的最大价值为："<<sum<<endl;
    	return 0;
    }