贪心算法（背包问题）NYOJ-106

朱雀 2022-06-05 10:35 197阅读 0赞

贪心算法

所谓贪心算法是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。

贪心算法不是对所有问题都能得到整体最优解，但对范围相当广泛的许多问题他能产生整体最优解或者是整体最优解的近似解。贪心算法的基本思路如下：

1.建立数学模型来描述问题。

2.把求解的问题分成若干个子问题。

3.对每一子问题求解，得到子问题的局部最优解。

4.把子问题的解局部最优解合成原来解问题的一个解。

例题：

描述

现在有很多物品（它们是可以分割的），我们知道它们每个物品的单位重量的价值v和重量w（1<=v,w<=10）；如果给你一个背包它能容纳的重量为m（10<=m<=20）,你所要做的就是把物品装到背包里，使背包里的物品的价值总和最大。

输入

第一行输入一个正整数n（1<=n<=5）,表示有n组测试数据；  
随后有n测试数据，每组测试数据的第一行有两个正整数s，m（1<=s<=10）;s表示有s个物品。接下来的s行每行有两个正整数v，w。

输出

输出每组测试数据中背包内的物品的价值和，每次输出占一行。

样例

3 15

5 10

2 8

3 9

输出

来源：

NYOJ

代码实现：

#include<stdio.h>
    #include<algorithm>
    using namespace std;
    /*定义结构体物品*/
    struct node
    {
        int v,w;//v为价值w为物品重量
    }a[101];
    int cmp(node A,node B)
    {
        return A.v>B.v;
    }
    int main()
    {
        int i,j,sum,s,m,n;
        scanf("%d",&n);
        while(n--)
        {
            sum=0;
            scanf("%d%d",&s,&m);//s为物品个数，m，为背包容量
            for(i=0; i<s; i++)
                scanf("%d%d",&a[i].v,&a[i].w);
            sort(a,a+s,cmp);
            /*贪心算法核心*/
            for(i=0; i<s; i++)
            {
                if(m<a[i].w)
                {
                    sum=sum+a[i].v*m;//背包可拆
                    m=0;
                    break;
                }
                else
                {
                    sum=sum+a[i].v*a[i].w;
                    m=m-a[i].w;
                }
            }
            printf("%d\n",sum);
        }
        return 0;
    }