首页 > 代码库 > 【贪心算法】背包问题

【贪心算法】背包问题

题目:有一个背包,背包容量是M=150。有7个物品,物品可以分割成任意大小。

要求尽可能让装入背包中的物品总价值最大,但不能超过总容量。

物品 A  B  C  D  E  F  G

重量 35  30  60  50  40  10  25

价值 10  40  30  50  35  40  30

思路:

让你把物品一个个的往包里装,要求装入包中的物品总价值最大,要让总价值最大,就可以想到怎么放一个个的物品才能让总的价值最大,因此可以想到如下三种选择物品的方法,即可能的局部最优解

①:每次都选择价值最高的往包里放。

②:每次都选择重量最小的往包里放。

③:每次都选择单位重量价值最高的往包里放。

找到可能的局部解以后,分析每一种解能不能合起来变成总体最优解,对以上三中局部解一一分析:

①:选择价值最高的,就会忽略了重量,若

M=50,

物品1: 重量:50,价值:40

物品2: 重量:20,价值30

物品3: 重量:30,价值30

显然,对于上述情况,该局部解行不通。

②:选择重量最小的,就会忽略了价值,同①策略类似。

③:该策略总是能让装入包中的物品总价值最大,所以该策略是正确的贪心策略。

注:(http://blog.csdn.net/a925907195/article/details/41314549该篇博客说第三种情况在一下情况是错的,

物品:A  B  C

重量:28 20 10

价值:28 20 10

其实该情况是符合贪心策略的,因为该总情况不管先选哪两个都会把背包塞满,因为该题物品可以分割成任意大小,所以,就算空下一下,也可以将最   后一个物品分割,放进去,它们   的单位重量的价值是一样的,所以,最后背包最后重量相同,重量相同那么价值也相同。

所以采用第三种策略,代码如下:

#include <iostream>
#include <algorithm>
using namespace std;
struct bag{
    int weight;
    int value;
    float bi;
    float bili;
}bags[100];
bool compare(const bag &bag1,const bag &bag2);
int main()
{
    int sum=0,n;
    float M;
    int j=0;
    cout<<"输入背包容量和物品种类数量:"<<endl;
    cin>>M>>n;
    for(int i=0;i<n;i++){
        cin>>bags[i].weight>>bags[i].value;
        bags[i].bi=bags[i].weight/bags[i].value;
    }
    for(int i=0;i<n;i++){
        bags[i].bili=0;
    }
    sort(bags,bags+n,compare);
   for(j=0;j<n;j++){
        if(bags[j].weight<=M){
            bags[j].bili=1;
            sum+=bags[j].weight;
            M-=bags[j].weight;
            cout<<"重:"<<bags[j].weight<<"价值:"<<bags[j].value<<"的物品被放入了背包"<<endl<<"比例:"<<bags[j].bili<<endl;
        }
        else break;
   }
   if(j<n){
    bags[j].bili=M/bags[j].weight;
    sum+=bags[j].bili*bags[j].weight;
    cout<<"重:"<<bags[j].weight<<"价值:"<<bags[j].value<<"被放入了背包"<<endl<<"比例:"<<bags[j].bili<<endl;
   }

    return 0;
}
bool compare(const bag &bag1,const bag &bag2){
return  bag1.bi>bag2.bi;
}

C++知识点总结:

①使用sort()函数需要在开头写,#include <algorithm>

②使用sort()比较结构体数组:

bool compare(const bag &bag1,const bag &bag2){
return  bag1.bi>bag2.bi;
}

 

 

 

 

 

 

 

 

 

 



【贪心算法】背包问题