• 可拆分背包问题(贪心算法)


    描述:

           这里有n种不同值v[i]和权重w[i]的对象(如果选择该对象的w[i]可以获得值v[i])。

      你有一个容器来挑选它们。你可以根据自己的需要把它们分成任意大小的碎片。可以拾取的对象的最大重量给定为w。请计算您能得到的最大值。

    输入:

           第一行输入n W(0<=n<=1000)(0<=W<=10000)

           第二行输入n个物品的价值(0<=v[i]<=10000)

      第三行输入n个物品的质量(0<=w[i]<=10000)

    输出:

           最大的价值,保留三位小数。

    分析:

      本题跟传统的0-1背包问题不同,本题中的物体可以分成任意份,所以我们可以运用贪心算法,根据物品的性价比(价值 / 质量)来解题,根据性价比的高低依次将物体放入背包中,当物体不能完全放入背包时,总价值 =   完全放入物品的价值 +  背包剩余空间 * 接下来应放入背包物品的性价比。

    代码:

    #include 
    #include 
    #include
    using namespace std;
    
    //需要一个结构体,通过性价比,能够查找到重量和价值。
    //做一个排序,需要将性价比由高到底排序,排序的过程中重量和(价值)要对应上
    
    typedef struct {
        double aver;
        double w;
        double v;
    }Knapsack;
    
    bool cmp(Knapsack a, Knapsack b)
    {
        return a.aver > b.aver;
    }
    int main()
    {
        Knapsack arrays[1009];
        int n;
        double m;
        double V = 0;
        cin >> n >> m;
        for (int i = 0; i < n; i++)
            cin >> arrays[i].v;
        for (int i = 0; i < n; i++)
            cin >> arrays[i].w;
    
    
        //求性价比
        for (int i = 0; i < n; i++)
        {
            arrays[i].aver = arrays[i].v / arrays[i].w;
            //cout << arrays[i].aver << endl;
        }
    
        //性价比排序
        sort(arrays, arrays + n, cmp);
      
        int sum = 0;
        for (int i = 0; i < n; i++)  //当背包能装下所有物品时,直接输出所有的物品价值之和
        {
            sum += arrays[i].w;
        }
        if (sum < m)
        {
            for (int j = 0; j < n; j++)
                V += arrays[j].v;
              //V = floor(V * 1000.0) / 1000.0;
            cout << setiosflags(ios::fixed) << setprecision(3) << V << endl;
            return 0;
        }
        //应该由性价比的顺序,通过容量,选择装入的物品
    
        for (int i = 0; i < n; i++) {
            if (arrays[i].w <= m)
            {
                V = V + arrays[i].v;
                m = m - arrays[i].w;
            }
            else {//直接将剩余的m加入即可
                V = V + m * arrays[i].aver;
                m = 0;
            }
            if (m == 0)
                break;
        }
        //V = floor(V * 1000.0) / 1000.0;
        cout << setiosflags(ios::fixed) << setprecision(3) << V << endl;
        return 0;
    }
     
  • 相关阅读:
    【面试经典150 | 哈希表】字母异位词分组
    nodeJs--url模块
    28道Webpack面试题及答案
    【软考学习8】操作系统概述、进程状态转变原理、前趋图
    Q3手机银行运营报告:直销银行江湖再起波澜,数字员工助力手机银行活跃度提升
    C语言 extern “C“的作用
    自制操作系统系列(四):进入64位模式
    【2023】Git版本控制-本地仓库详解
    文献认证!Kamiya艾美捷抗酒石酸酸性磷酸酶TRAP染色试剂盒
    【学习笔记23】JavaScript数组的遍历方法
  • 原文地址:https://blog.csdn.net/liuliuhelingdao/article/details/128057773