c语言贪心算法分糖果

// 贪心算法分糖果
int candy(int* ratings, int ratingsSize) {
    int* candies = (int*)malloc(sizeof(int) * ratingsSize);
    for (int i = 0; i < ratingsSize; i++) {
        candies[i] = 1;
    }
    for (int i = 1; i < ratingsSize; i++) {
        if (ratings[i] > ratings[i - 1]) {
            candies[i] = candies[i - 1] + 1;
        }
    }
    for (int i = ratingsSize - 1; i > 0; i--) {
        if (ratings[i - 1] > ratings[i] && candies[i - 1] <= candies[i]) {
            candies[i - 1] = candies[i] + 1;
        }
    }
    int sum = 0;
    for (int i = 0; i < ratingsSize; i++) {
        sum += candies[i];
    }
    free(candies);
    return sum;
}

相关问题

c语言贪心算法的基本思想

C语言贪心算法的基本思想是在每一步选择中都采取当前状态下最优的选择，从而希望导致结果是全局最优的。贪心算法通常需要满足两个条件：最优子结构和贪心选择性质。最优子结构指的是问题的最优解包含子问题的最优解，而贪心选择性质则是指每一步的最优解都可以通过之前的最优解得到。

在实际应用中，贪心算法常用于求解最小生成树、最短路径、背包问题等。但是需要注意的是，贪心算法并不是万能的，有些问题使用贪心算法得到的结果并不一定是全局最优解。

C语言贪心算法背包问题

好的，关于C语言贪心算法背包问题，我可以给你一些基本的思路和代码实现。

首先，背包问题是一个经典的动态规划问题，但是在某些情况下，使用贪心算法也可以得到较好的解。对于背包问题，我们可以将物品按照单位重量的价值从大到小排序，然后依次将物品放入背包中，直到背包装满或者所有物品都放完为止。

下面是C语言实现贪心算法解决背包问题的代码：

#include <stdio.h>
#include <stdlib.h>

#define MAX_N 1000

typedef struct {
    int w;  // 物品重量
    int v;  // 物品价值
    double r;  // 单位重量价值
} Item;

int cmp(const void *a, const void *b) {
    Item *ia = (Item *)a;    Item *ib = (Item *)b;
    return ib->r > ia->r ? 1 : -1;
}

double knapsack(Item items[], int n, int W) {
    qsort(items, n, sizeof(Item), cmp);  // 按照单位重量价值从大到小排序
    double value = 0.0;  // 背包中物品的总价值
    int i;
    for (i = 0; i < n && W > 0; i++) {
        if (items[i].w <= W) {  // 物品可以全部放入背包中
            value += items[i].v;
            W -= items[i].w;
        } else {  // 物品只能部分放入背包中
            value += items[i].r * W;
            W = 0;
        }
    }
    return value;
}

int main() {
    int n, W;
    Item items[MAX_N];
    printf("请输入物品数量和背包容量：");
    scanf("%d%d", &n, &W);
    printf("请输入每个物品的重量和价值：\n");
    int i;
    for (i = 0; i < n; i++) {
        scanf("%d%d", &items[i].w, &items[i].v);
        items[i].r = (double)items[i].v / items[i].w;  // 计算单位重量价值
    }
    double value = knapsack(items, n, W);
    printf("背包中物品的总价值为：%.2f\n", value);
    return 0;
}