最优装载问题（贪心基础）

淩亂°似流年 2022-06-07 08:42 191阅读 0赞

最优装载问题。给出n个物体，第i个物体重量为w\[i\]。选择尽量多的物体，使得总重量不超过C。  
【分析】  
由于只关心物体的数量，所有装重的没有装轻的划算。只需把所有物体按重量从小到大排序，一次选择每个物体，直到装不下为止。这是一种典型的贪心算法，只顾眼前，但能得到最优解。

#include <iostream>
    using namespace std;
    
    //交换 
    template <class type>
    void swap2(type &x, type &y) {
        type temp = x;
        x = y;
        y = temp;
    }
    
    //冒泡排序 
    void sort2(int *box, int n) {
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                if (box[i] > box[j]) {
                    swap2(box[i],box[j]);
                } 
            }
        }
    }
    
    //贪心算法装载 
    void loading(int *box, int *r, int c, int n) {
        for (int i = 0; i < n; i++)  
        {  
            if (c-box[i] >= 0){  
                c -= box[i];  
                r[i] = box[i];  
            }  
        }  
    
    }
    
    int main() {
    
        int c = 100;  //载重容量
        int box[6]={
       100,20,25,25,20,20};    //重量
        int result[6] = {
       0};
    
        sort2(box,6);
    
        loading(box,result,c,6);
        for (int i = 0; i < 6; i++) {
            if (result[i] == 0) break; 
            cout << result[i] << " "; 
        }
    
        return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，191人围观）

还没有评论，来说两句吧...

相关阅读

相关最优装载--动态规划

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ub

浅浅的花香味﹌/ 2023年07月24日 13:24/ 0 赞/ 12 阅读

相关【贪心算法】最优装载问题C++语言

文章目录问题描述问题分析算法步骤举例代码问题描述

àì夳堔傛蜴生んèń/ 2023年03月12日 12:13/ 0 赞/ 190 阅读

相关算法设计与分析——贪心算法——最优装载问题

有一批集装箱要装上一艘载重量为c的轮船。其中集装箱i的重量为Wi。最优装载问题要求确定在装载体积不受限制的情况下，将尽可能多的集装箱装上轮船。 include<ios

电玩女神/ 2023年01月16日 11:28/ 0 赞/ 202 阅读

相关（贪心算法）PTA--最优合并问题

给定k 个排好序的序列, 用 2 路合并算法将这k 个序列合并成一个序列。假设所采用的 2 路合并算法合并 2 个长度分别为m和n的序列需要m+n-1 次比较。试设计一个算

小鱼儿/ 2022年12月27日 12:35/ 0 赞/ 141 阅读

相关回溯法装载问题java最优解,回溯法最优装载问题（java）

1.问题描述：有一批共有 n 个集装箱要装上两艘载重量分别为 c1 和 c2 的轮船，其中集装箱 i 的重量为 w\[i\], 且重量之和小于(c1 + c2)。装载问题要

超、凢脫俗/ 2022年11月17日 03:58/ 0 赞/ 193 阅读

相关贪心算法（最优装载问题）

加勒比海盗船海盗们截获了一艘装满各种各样古董的货船，每一件古董都价值连城，一旦打碎就失去了它的价值。虽然海盗船足够大，但载重量为 C ，每件古董的重量为 W

古城微笑少年丶/ 2022年09月10日 03:30/ 0 赞/ 309 阅读

相关最优装载问题（贪心基础）

最优装载问题。给出n个物体，第i个物体重量为w\[i\]。选择尽量多的物体，使得总重量不超过C。【分析】由于只关心物体的数量，所有装重的没有装轻的划算。只需把所有物

淩亂°似流年/ 2022年06月07日 08:42/ 0 赞/ 192 阅读

相关贪心算法1：贪心的概念最优装载问题

> 贪心算法的原理：贪心算法总是做出当前最好的选择，也就是说，它期望通过局部最优选择从而得到全局最优的解决方案。 1. 没有后悔药，一旦做出选择，不可以后悔； 2. 有

谁借莪１个温暖的怀抱￠/ 2022年05月08日 10:08/ 0 赞/ 307 阅读

相关贪心算法（3）：最优服务次序问题

题目设有n个顾客同时等待一项服务。顾客i需要的服务时间为ti, 1≦i ≦n 。有1处可以提供此服务。应如何安排n个顾客的服务次序才能使平均等待时间达到最小?平均等待时

拼搏现实的明天。/ 2022年02月04日 04:09/ 0 赞/ 378 阅读

相关最优分解问题（C语言）--贪心策略

最优分解问题题目描述设n是一个正整数，现在要求将n分解为若干个互不相同的自然数的和，使这些自然数的乘积最大。解题思路根据数学中和定近积大，积定近和小的

忘是亡心i/ 2022年01月05日 10:13/ 0 赞/ 275 阅读