贪心算法-背包问题

背包问题

**已知容量为M的背包和n件物品。第i件物品的重量为wi，价值是pi，且将物品i的一部分xi放进背包即可以获得pi*xi的价值。那么，怎么装包才能获得最大价值？**

若采用贪心算法，有如下几种方案可选：

• 1、每次选择最轻的物品；
• 2、每次选择最大价值的物品；

• 3、每次选择性价比最大的物品，即pi/wi最大。

  方案1只考虑多装物品，但由于性价比不一定高，故总价值可能不是最大；方案2忽略了物品的重量，每次选择的价值虽大，但装的物品比较少；事实证明方案3能够达到总价值最大。

  C语言实现

// 贪心算法-背包问题.cpp : 定义控制台应用程序的入口点。
#include "stdafx.h"
#include <algorithm>
using namespace std;
#define N 3
typedef struct 
{
    int w;//重量
    int v;//价值
    double c; //性价比
}bag;
bool cmp(bag a, bag b)
{
    return a.c > b.c;
}
double GreedyKnapsack(bag a[], int n, double weight)
{ //返回最大价值
    double c_left = weight;  //背包的剩余容量
    int i = 0;
    double b = 0; //获得的价值
    while (i < n&&a[i].w < c_left)
    { //能够放下整个的物品时
        c_left = c_left - a[i].w;
        b = b + a[i].v;
        ++i;
    }
    if (i < n)
    {//只能放下物品的一部分时
        b = b + a[i].v*(c_left / a[i].w);
    }
    return b;
}
int main()
{
    int sum_weight;
    double value;  // 书包所能容纳的最大价值
    printf("请输入书包的负重：");
    scanf_s("%d", &sum_weight);

    bag bags[N];
    printf("请依次输入%d种物品的重量和价值:\n",N);
    for (int i = 0; i < N; i++)
    {
        scanf_s("%d", &bags[i].w);
        scanf_s("%d", &bags[i].v);
        bags[i].c = (bags[i].v*1.0) / bags[i].w;
    }
    //测试用例 
    //bags[0].w = 4;
    //bags[0].v = 2;
    //bags[0].c = 0.5;

    //bags[1].w = 2;
    //bags[1].v = 6;
    //bags[1].c = 3.0;

    //bags[2].w = 4;
    //bags[2].v = 4;
    //bags[2].c = 1.0;
    sort(bags, bags + N, cmp);
    value=GreedyKnapsack(bags, N, sum_weight);
    printf("该书包所能容纳的最大价值是：%.2f\n", value);
    return 0;
}