部分背包问题（贪心算法）

部分背包问题是基于贪心法的基本思想。

何谓贪心法，只要你够贪心，就能领略贪心算法之精髓。

部分背包问题和0/1背包问题的区别就是：部分背包问题中的单个物品，可以取一部分装入背包。而0/1背包问题则是要么全部拿走，要么一无所有（这里引用了LOL卡牌大师的台词）。那么作为一个so greed的你，肯定应该知道按照什么顺序拿物品的把。没错，看着值钱的先抢！这里所说的值钱，指的是单位重量所产生的价值越大（即value/weight的比值越大）。那么问题很简单咯~，把"值钱"的东西排在前面，每次拿抢的时候，问问看背包君够不够承受得住，承受的了，就全部抢过来。承受不住，那么只能按照所能承受的重量，取物品的一部分了。当然价值也得按照比例来哦~

/************************************************************************
*
* 文件名：背包问题.cpp
*
* 文件描述：要求用贪心算法去解决背包问题，这种类型的背包问题比0-1背包问题好解决，一般只需要
*           用价值除以重量然后按照从大到小的顺序依次装入就行了直至背包装满。
*
* 创建人：  fdk

* 时  间：  2018-11-08
*
* 版本号：1.0
*
* 修改记录：
*
************************************************************************/

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<string>
#include<vector>
#include<stack>
#include<bitset>
#include<cstdlib>
#include<cmath>
#include<set>
#include<list>
#include<deque>
#include<map>
#include<queue>
#include<limits.h>
#define max 100
using namespace std;

/*排序函数，将物品按照从大到小排序（价值/重量）*/
void swap (float ave[], int s[], int n)
{
    int i, j;
    for (i = 0; i < n; i++)
    {
        for (j = i+1; j < n; j++)
        {
            /*如果前面的值小于后面的值则调换位置*/
            if (ave[s[i]] <= ave[s[j]])
            {
                /*注意这里互换的是下标并不是真正的值，因为后面还要用到重量*/
                int temp = s[i];
                s[i] = s[j];
                s[j] = temp;
            }
        }
    }
}

/*求背包的最大价值*/
void bag (float w[], float p[], int s[], float volume, int n)
{
    int i;
    float totalV = 0; //总价值
    for (i = 0; i < n; i++)
    {
        /*如果当前的容量能装下i物品，则全部装入*/
        if (volume >= w[s[i]])
        {
            volume -= w[s[i]]; //背包的容量减去装入的重量
            totalV += p[s[i]]; //将当前背包的价值加上装入的物品的价值
            cout << "重量为" << w[s[i]] << ",价值为" << p[s[i]] << "的物品被全部拿走" << endl;
        }
        else
        {
            /*如果不能全部装入则装入部分直至全部装满*/
            totalV += volume/ w[s[i]] * p[s[i]]; //相应的价值按照相应的比例乘以重量
            cout << "重量为" << w[s[i]] << ",价值为" << p[s[i]] << "的物品拿走" << volume / w[s[i]] << endl;
            volume = 0;
            break;
        }
    }
    cout << "能装满的最大价值为：" << totalV << endl;
}
int main()
{
    int s[20], i;
    float w[20], p[20]; //w为重量，p为价值

    cout << "请输入最大重量：" << endl;
    float volume; //最大重量
    cin >> volume;

    cout << "请输入商品的种类数量：" << endl;
    int n; //商品种类数量
    cin >> n;

    cout << "请输入各个商品的重量和价值：" << endl;
    for (i = 0; i < n; i++)
    {
        cin >> w[i] >> p[i];
    }

    float ave[20]; //ave为单位重量上的价值
    for (i = 0; i < n; i++)
    {
        ave[i] = p[i] / w[i]; //重量除以价值
    }

    for (i = 0; i < n; i++)
    {
        /*下标函数*/
        s[i] = i;
    }

    swap(ave, s, n);
    bag(w, p, s, volume, n);
    return 0;
}

测试用例：

30 6

10 12
9 9
11 7
12 9
7 8
3 4

输出结果：

部分背包问题（贪心算法）

参考博客：https://blog.****.net/mll1208596630/article/details/50358286

部分背包问题（贪心算法）

相关推荐