背包问题（C语言实现）

生活中我们去看望朋友时会带一些礼物，自己只能背一定重量的背包，想带的东西又特别多，只能选择几样价值高而且总重量在自己所能承受的范围内的物品。

本文将介绍使用C语言实现背包问题的求解方法，背包问题也是数据结构与算法中的经典问题。

问题描述

有 N 件物品和一个规定了重量上限 W 的背包，每件物品的价值是 v，求解将哪些物品装入背包可使这些物品的重量之和不超过背包限重，且价值总和最大。

问题分析及实现

由问题描述可知，我们要实现的是从 N 件物品中找出价值总和最大，但又不超过背包限重 W 的值的解。简单举例：有两件物品，A 物品和 B 物品，重量分别是 30、35，价值分别是 40、20，背包限重 W 为 40，此时，我们的解应该是选 A 物品。

问题分析

我们将要开发的程序，就是采用一定的算法取得最优解，即重量不超过背包限重，但取得的价值最大。

为了能够实现这一算法，我们采用贪心算法，背包问题也分很多种，贪心算法解决的是物品可以拆分的背包问题，所以在此用这个算法比较容易理解、实现。

贪心算法是指对所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，目前所做出的选择是在某种意义上的局部最优解。这是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的主要区别。

背包问题最重要之处就在于每一次选择的物品都是放入的最佳选择。

什么是最佳选择呢？通过我们了解的数学知识可以认为，每一次最佳选择就是每次放入的物品是目前未选择物品中价值最大且质量最小的，这里就要引入一个衡量物品的属性——物品的单位重量价值，即该物品的价值除以该物品的重量。

所以，背包问题的每一次的最佳选择就是要每次选出物品的单位重量价值最大的物品。

既然物品的单位重量价值非常重要，我们可以把它作为一个基本数据项存储在物品信息中，当用户从键盘上输入物品重量和价值后，计算出该值并保存起来，以备后面使用。

为了方便最优解的选择，下一步我们可以先按每个物品的单位重量价值做降序排列，在最后挑选物品时就可以按单位重量价值从高到低把物品放入背包，直到超重为止，之前选择放入的物品就是要求的最优解。

C语言实现背包问题

本文通过C语言求解背包问题，实现的代码如下。

采用结构体保存物品信息

通过定义一个结构体类型来记录物品的序号、重量、价值和单位重量价值。代码如下。

#include <stdio.h>
#define N 100         /*物品总种数*/
int nType;                 /*输入的物品数*/
int SelectNumber;         /*选中物品的数量，即单位重量价值降序排列后的前几个物品*/
float MaxValue;        /*选中物品的总价值*/
float TotalWeight;         /*选中物品的总重量 */
float LimitWeight;         /*输入的限制总重量 */
struct  goods        /*物品结构*/
{ 
    int order;         /*物品序号*/
    float weight;         /*物品重量*/
    float value;         /*物品价值*/
    float UnitValue;          /*物品单位重量价值*/
}good[N];

选择物品最优解函数

此函数主要以贪心算法判断并找出一个最优解。

按照已降序排列的所有物品的单位重量价值，把排在前面的物品的重量累加在一起不超过限重的物品就是被选中的物品，其余物品不选。C语言编程代码如下。

void CheckOut(struct goods g[] ,int num,float tw)   /*检查排序后的物品集中选择多少个物品不超过限重*/
{
    int i;
    SelectNumber=0;
    TotalWeight=0.0;
    MaxValue=0.0;
    for(i=0;i<num;i++)
        if(TotalWeight+g[i].weight <=tw )   /*从已排序的物品中选出一个物品，测试增加一个物品后是否超过限重*/
        {
            MaxValue+=g[i].value;
            TotalWeight=TotalWeight+g[i].weight;
            SelectNumber++;
        }
        else   /*一旦超重则停止对后面物品的选择，退出循环，结束函数执行*/
            break;
}

按所有物品的单位重量价值降序排列函数

利用选择排序法对所有输入的物品按照单位重量价值降序排序，以便下一步选择最优解。

排序时注意每轮选出最大单位重量价值的物品后，要与本轮比较的顶部数据交换物品所有数据项的信息，包括序号、重量、价值、单位重量价值。C语言编程代码如下。

void sort(struct goods g[] ,int num)                  /*对所有物品单位重量价值按降序排列*/
{
    float temp,max;
    int i,j,flag,position,temporder;
    for(i=0;i<num-1;i++)
    {   max=g[i].UnitValue;
        flag=0;
        for(j=i+1;j<num;j++)
            if(max<g[j].UnitValue)
            {   position=j;
                max=g[j].UnitValue;
                flag=1;
            }
        if(flag)
        {   temp=g[i].UnitValue;                     /*交换单位重量价值*/
            g[i].UnitValue=max;
            g[position].UnitValue=temp;
            temp=g[i].value;                       /*交换价值*/
            g[i].value=g[position].value;
            g[position].value=temp;
            temp=g[i].weight;                      /*交换重量*/
            g[i].weight=g[position].weight;
            g[position].weight=temp;   
            temporder=g[i].order;                   /*交换序号*/
            g[i].order=g[position].order;
            g[position].order=temporder;
        }
    }
}

主函数

主程序开始运行，要求用户输入物品种类数、背包限重、每个物品的序号、重量、价值。然后调用按所有物品的单位重量价值降序排序函数，再调用选择物品函数，输出最终选择的最优解。代码如下。

int main()
{
    int i;
    printf("请输入物品类别个数:");
    scanf("%d",&nType);
    printf("请输入背包限重的重量:");
    scanf("%f",&LimitWeight);
    printf("\n请输入各物品的重量和价值:\n");
    for(i=0;i<nType;++i)
    {
        printf("第%d个物品重量:",i+1);
        scanf("%f",&good[i].weight);
        printf("第%d个物品价值:",i+1);
        scanf("%f",&good[i].value);
        good[i].UnitValue=good[i].value/good[i].weight;
        good[i].order=i;
    }
    printf("\n输入的物品有：\n");
    printf("序号  重量    价值\n");   
    for(i=0;i<nType;i++)
        printf("%3d   %.2f   %.2f\n",good[i].order+1,good[i].weight,good[i].value);
    sort(good,nType);                          /*对物品按单位重量价值降序排列*/
    CheckOut(good,nType,LimitWeight);               /*调用选择物品函数*/
    printf("\n被选中的物品有：\n");
    printf("序号  重量    价值\n");
    for(i=0;i<SelectNumber;i++)   
        printf("%3d   %.2f   %.2f\n",good[i].order+1,good[i].weight,good[i].value);
    printf("合计总价值为: %f\n",MaxValue);
}  

程序运行：

请输入物品类别个数:4
请输入背包限重的重量:100

请输入物品类别个数:4
请输入背包限重的重量:100

请输入各物品的重量和价值:
第1个物品重量:38.0
第1个物品价值:130
第2个物品重量:30.0
第2个物品价值:200
第3个物品重量:35.0
第3个物品价值:150
第4个物品重量:30.0
第4个物品价值:280

输入的物品有：
序号  重量    价值
  1   38.00   130.00
  2   30.00   200.00
  3   35.00   150.00
  4   30.00   280.00

被选中的物品有：
序号  重量    价值
  4   30.00   280.00
  2   30.00   200.00
  3   35.00   150.00
合计总价值为: 630.000000

程序首先要求用户输入物品数、背包限重，并输入每个物品对应的序号、价值和重量，计算出单位重量价值，然后对所有物品按单位重量价值降序排列，下一步找出最优解，最后输出结果。

背包问题有两种经典算法：动态规划算法和贪心算法。

动态规划算法需要采用递归函数，但是递归概念不易理解，特别是本程序数据结构比较复杂，代码看上去比较杂乱。

贪心算法比较适合我们要解决的问题，易理解，代码实现比较简单，所以在此我们采用了贪心算法。