小目标

用户名：LZYLZYLZY

访问量：7347

签　名：

等　　级
排　　名	1405
经　　验	2911
参赛次数	1
文章发表	8
年　　龄	0
在职情况	学生
学　　校	四川农业大学
专　　业

　　自我简介：

TA的其他文章

[编程入门]自定义函数之整数处理-题解(C语言代码)
浏览：486

[编程入门]三个字符串的排序-题解(C语言代码)
浏览：3451

[编程入门]C语言循环移位-题解(C语言代码)
浏览：571

你可能喜欢

C语言程序设计教程（第三版）课后习题6.9 （C++代码）论pow函数的应用

C语言程序设计教程（第三版）课后习题6.11 （C++代码）（有个库函数叫sqrt）

贪心算法（含例题）

　　作者: 小目标　　　　发表时间：2019-07-11 20:27:08 浏览：598　|　评论：0　

一.基本思想

1.内容：指从问题的初始状态出发，通过多次的贪心选择，最终得到整个问题的最优解。

2.贪心策略：通常会将问题切分成不同的阶段，并通过一系列的贪心选择来得到一个问题的最优解。而每一次的选择都是当前状态的一种最优选择，即贪心 选择。通常只考虑当前局部最优的策略，最终得到全局的最优解。

3.使用条件：▪有最优子结构：即一个问题的最优解包含其子问题的最优解。
▪满足贪心选择性质：所求问题的整体最优解可以通过一系列局部最优的选择来达到。

4.算法核心：如何设计贪心选择并证明其争取性。

例题：圣诞老人的礼物
描述：圣诞节来临了，在城市A中圣诞老人准备分发糖果，现在有多箱不同的糖果，每箱糖果有自己的价值和重量，每箱糖果都可以拆分成任意散装组合带走。圣诞老人的驯鹿最多只能承受一定重量的糖果，请问圣诞老人最多能带走多大价值的糖果。

输入：第一行由两个部分组成，分别为糖果箱数正整数n(1 <= n <= 100)，驯鹿能承受的最大重量正整数w（0 < w < 10000），两个数用空格隔开。其余n行每行对应一箱糖果，由两部分组成，分别为一箱糖果的价值正整数v和重量正整数w，中间用空格隔开。

输出：输出圣诞老人能带走的糖果的最大总价值，保留1位小数。输出为一行，以换行符结束

样例输入
4 15
100 4
412 8
266 7
591 2
样例输出
1193.0

```c
#include <stdio.h>
#include <stdlib.h>
int a[100][2];  //记录每一箱的价值和重量
float b[100];  //每一箱的单位价值

int main()
{
    int n,w,i,j,k;
    float t,sum=0;
    scanf("%d %d",&n,&w);
    for(i=0;i<n;i++)
    {
        scanf("%d %d",&a[i][0],&a[i][1]);
        b[i] = a[i][0]*1.0/a[i][1];
    }

for(i=0;i<n;i++)  //按单位价值从高到低进行排序，并在单位价值进行交换时，连带对应的每箱糖果的价值和重量交换。
    {
        for(j=0;j<i;j++)
        {
            if(b[i] > b[j])
            {
                t = b[i];
                b[i] = b[j];
                b[j] = t;
                k = a[i][1];
                a[i][1] = a[j][1];
                a[j][1] = k;
                k = a[i][0];
                a[i][0] = a[j][0];
                a[j][0] = k;
            }
        }
    }
    i = 0;
    while(w > 0)
    {
        sum += a[i][0];
        w -= a[i][1];
        i++;
    }
    if(w < 0)  //当装入的重量大于能承受的最大重量时，将超出部分的价值减掉
    {
        sum += w*b[i-1];
    }

printf("%.1f\n",sum);
    return 0;
}
```

0.0分

1 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

小目标

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题8.7 （C++代码）

C语言程序设计教程（第三版）课后习题6.9 （C++代码）论pow函数的应用

点我有惊喜！你懂得！

【蟠桃记】（C++代码）（递归计算）

C语言程序设计教程（第三版）课后习题6.11 （C++代码）（有个库函数叫sqrt）

贪心算法（含例题）

评论区

精彩推荐

C语言考试练习题_保留字母（C语言代码）

破解简单密码（C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

C语言训练-求1+2!+3!+...+N!的和（C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

分糖果（C++代码）

C语言程序设计教程（第三版）课后习题6.9 （C语言代码）

C语言程序设计教程（第三版）课后习题9.3 （C语言代码）

A+B for Input-Output Practice (VI) （C语言代码）

C语言程序设计教程（第三版）课后习题11.1 （C语言代码）

小目标

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题8.7 （C++代码）

C语言程序设计教程（第三版）课后习题6.9 （C++代码）论pow函数的应用

点我有惊喜！你懂得！

【蟠桃记】 （C++代码）（递归计算）

C语言程序设计教程（第三版）课后习题6.11 （C++代码）（有个库函数叫sqrt）

贪心算法（含例题）

评论区

精彩推荐

C语言考试练习题_保留字母 （C语言代码）

破解简单密码 （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

C语言训练-求1+2!+3!+...+N!的和 （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

分糖果 （C++代码）

C语言程序设计教程（第三版）课后习题6.9 （C语言代码）

C语言程序设计教程（第三版）课后习题9.3 （C语言代码）

A+B for Input-Output Practice (VI) （C语言代码）

C语言程序设计教程（第三版）课后习题11.1 （C语言代码）

【蟠桃记】（C++代码）（递归计算）

　　评论区

C语言考试练习题_保留字母（C语言代码）

破解简单密码（C语言代码）

C语言训练-求1+2!+3!+...+N!的和（C语言代码）

分糖果（C++代码）