2025年【C语言】——背包问题详解「建议收藏」

编程汇总 • 2025-09-03 20:06 • 阅读 58

1.题目描述：——背包问题

有若干物品，每种物品的价值和重量各不相同，将物品装入一个容量有限的背包，如何选择装入的物品，使背包的价值最大。

2.题目分析：

要是背包中的物品价值最大，则需要在有限的重量中尽可能装入价值更大的物品，基于这种思想则采取贪心算法
首先计算物品的单位价值，即价值/重量，根据单位价值对物品进行排序，优先装入单位价值高的物品，直至背包装满。

3.代码实现：

#include 

int n;//物品数量

double c;//背包容量

double v[999];//物品的价值

double w[999];//物品的重量

double cw = 0.0;//背包重量

double cp = 0.0;//背包价值

double bestp = 0.0;//当前最优价值

double perp[999];//物品性价比排序

int order[100];//物品编号

int put[100];//装入标识

void sort()

{

   int i,j;

   int temporder = 0;

   double temp= 0.0;

   for(i=1;i<=n;i++)

       perp[i]=v[i]/w[i];

   for(i=1;i<=n-1;i++)

    {

       for(j=i+1;j<=n;j++)

           if(perp[i]
       {

           temp = perp[i];

           perp[i]=perp[j];

           perp[j]=temp;

           temporder=order[i];

           order[i]=order[j];

           order[j]=temporder;

           temp = v[i];

           v[i]=v[j];

           v[j]=temp;

           temp=w[i];

           w[i]=w[j];

           w[j]=temp;

       }

    }

}

void backtrack(int i)

{

    double bound(int i);

   if(i>n)

    {

       bestp = cp;

       return;

    }

   if(cw+w[i]<=c)

    {

       cw+=w[i];

       cp+=v[i];

       put[i]=1;

       backtrack(i+1);

       cw-=w[i];

       cp-=v[i];

    }

   if(bound(i+1)>bestp)

       backtrack(i+1);

}

double bound(int i)

{

    double leftw= c-cw;

    double b =cp;

   while(i<=n&&w[i]<=leftw)

    {

       leftw-=w[i];

       b+=v[i];

       i++;

    }

   if(i<=n)

       b+=v[i]/w[i]*leftw;

    return b;

}

int main()

{

   int i;

   printf("请输入物品的数量和容量：");

   scanf("%d%lf",&n,&c);

   for(i=1;i<=n;i++)

    {

       printf("第%d个物品的重量和价值：",i);

       scanf("%lf %lf",&w[i],&v[i]);

       order[i]=i;

    }

   sort();

   backtrack(1);

   printf("最大价值为：%lf\n",bestp);

   printf("装入的物品次序为：");

   for(i=1;i<=n;i++)

    {

       if(put[i]==1)

           printf("%d ",order[i]);

    }

    return 0;

}

2025年【C语言】——背包问题详解「建议收藏」

相关推荐