背包问题-C语言实现

浏览数：22 / 时间：2015年06月08日

转自：http://blog.csdn.net/tjyyyangyi/article/details/7929665

 

0-1背包问题

参考:

动态规划解法

借个图 助于理解

技术分享

从背包容量为0开始,1号物品先试,0,1,2,的容量都不能放.所以置0,背包容量为3则里面放4.这样,这一排背包容量为 4,5,6,....10的时候，最佳方案都是放4.假如1号物品放入背包.则再看2号物品.当背包容量为3的时候，最佳方案还是上一排的最价方案c为 4.而背包容量为5的时候，则最佳方案为自己的重量5.背包容量为7的时候，很显然是5加上一个值了。加谁??很显然是7-4=3的时候.上一排 c3的最佳方案是4.所以。总的最佳方案是5+4为9.这样.一排一排推下去。最右下放的数据就是最大的价值了。(注意第3排的背包容量为7的时候,最佳 方案不是本身的6.而是上一排的9.说明这时候3号物品没有被选.选的是1,2号物品.所以得9.)

[cpp] view plaincopy
  1. #include<stdio.h>  
  2.   
  3. int f[10][100];  
  4. //构造最优矩阵  
  5. void package0_1(int *w,int *v,int n,int c)  
  6. {  
  7.     int i,j;  
  8.     //初始化矩阵  
  9.     for(i=1;i<=n;i++)  
  10.         f[i][0] = 0;  
  11.     for(j=1;j<=c;j++)  
  12.         f[0][j] = 0;      
  13.       
  14.     for(i=1;i<=n;i++)  
  15.     {  
  16.         for(j=1;j<=c;j++)  
  17.         {  
  18.             //当容量够放入第i个物品，并且放入之后的价值要比不放大  
  19.             if(w[i] <= j && f[i-1][j-w[i]] + v[i] > f[i-1][j])  
  20.             {  
  21.                 f[i][j] = f[i-1][j-w[i]] + v[i];              
  22.             }else  
  23.                 f[i][j] = f[i-1][j];  
  24.         }  
  25.     }     
  26.     printf("最大价值: %d \n",f[n][c]);  
  27. }  
  28.   
  29. //构造最优解  
  30. void getResult(int n,int c,int *res,int *v,int *w)  
  31. {  
  32.     int i,j;  
  33.     j = c;  
  34.     for(i=n;i>=1;i--)  
  35.     {  
  36.         if(f[i][j] != f[i-1][j])  
  37.         {  
  38.             res[i] = 1;  
  39.             j = j - w[i];  
  40.         }  
  41.     }  
  42. }  
  43.   
  44. void main()  
  45. {  
  46.     int w[6] = {0,2,2,6,5,4};//每个物品的重量  
  47.     int v[6] = {0,6,3,5,4,6};//每个物品的价值  
  48.     int res[5] = {0,0,0,0,0};  
  49.     int n = 5; //物品的个数  
  50.     int c = 10; //背包能容的重量  
  51.     int i,j;  
  52.     package0_1(w,v,n,c);  
  53.     for(i=0;i<=n;i++)  
  54.     {  
  55.         for(j=0;j<=c;j++)  
  56.             printf("%2d ",f[i][j]);  
  57.         printf("\n");  
  58.     }  
  59.     getResult(n,c,res,v,w);  
  60.     printf("放入背包的物品为: \n");  
  61.     for(i=1;i<=n;i++)  
  62.         if(res[i] == 1)  
  63.             printf("%d  ",i);  
  64. }  


0-1背包的递归解法

[cpp] view plaincopy
  1. #include<stdio.h>  
  2.   
  3. int maxNum[6];  //存放最优解的编号  
  4. int maxValue=0; //存放最大价值  
  5. int w[6] = {0,2,2,6,5,4};//每个物品的重量，第一个为0，方便角标对应  
  6. int v[6] = {0,6,3,5,4,6};//每个物品的价值，第一个为0，方便角标对应  
  7. int num = 5; //物品的个数    
  8. int cap = 10; //背包能容的重量     
  9.   
  10. void package01(int *flag,int n,int c,int nowValue)  
  11. {  
  12.     int i;  
  13.     if(n == 0 || c == 0)  
  14.     {  
  15.         if(nowValue > maxValue)  
  16.         {     
  17.             for(i=0;i<6;i++)  
  18.                 maxNum[i] = flag[i];   
  19.             maxValue = nowValue;  
  20.         }  
  21.         return;  
  22.     }  
  23.       
  24.     if(c >= w[n])  
  25.     {  
  26.         flag[n] = 1;  
  27.         package01(flag, n-1, c-w[n], nowValue+v[n]);  
  28.     }  
  29.     flag[n] = 0;  
  30.     package01(flag, n-1, c, nowValue);    
  31. }  
  32.   
  33. void main()  
  34. {  
  35.     int flag[6] = {0,0,0,0,0,0};    
  36.     int i;    
  37.     package01(flag,num,cap,0);    
  38.     for(i=1;i<=num;i++)  
  39.         maxNum[i] == 1 ? printf("第%d号货物装了包中  \n",i) : 0;  
  40.     printf("最大价值为:%d  \n",maxValue);  
  41. }  


 


 完全背包问题

与0-1背包问题区别在每个物品有无限多个。

[cpp] view plaincopy
  1. #include<stdio.h>     
  2.   
  3. int f[10][100];    
  4. //构造最优矩阵     
  5. void package0_1(int *w,int *v,int n,int c)    
  6. {    
  7.     int i,j,k;    
  8.     //初始化矩阵     
  9.     for(i=1;i<=n;i++)    
  10.         f[i][0] = 0;    
  11.     for(j=1;j<=c;j++)    
  12.         f[0][j] = 0;        
  13.       
  14.     for(i=1;i<=n;i++)    
  15.     {    
  16.         for(j=1;j<=c;j++)    
  17.         {    
  18.             //当容量够放入k个第i个物品，并且放入之后的价值要比不放大     
  19.             k = j/w[i];  
  20.             if( k>0 && (f[i-1][j- k * w[i]] +  k * v[i] > f[i-1][j]))    
  21.             {    
  22.                 f[i][j] = f[i-1][j- k * w[i]] +  k * v[i] ;           
  23.             }else    
  24.                 f[i][j] = f[i-1][j];    
  25.         }    
  26.     }       
  27.     printf("最大价值: %d \n",f[n][c]);    
  28. }    
  29.   
  30. //构造最优解     
  31. void getResult(int n,int c,int *res,int *v,int *w)    
  32. {    
  33.     int i,j;    
  34.     j = c;    
  35.     for(i=n;i>=1;i--)    
  36.     {    
  37.         while(f[i][j] > f[i-1][j])    
  38.         {    
  39.             res[i] ++;    
  40.             j = j - w[i];    
  41.         }    
  42.     }    
  43. }    
  44.   
  45. void main()    
  46. {    
  47.     int w[6] = {0,4,6,6,3,6};//每个物品的重量     
  48.     int v[6] = {0,1,1,1,2,1};//每个物品的价值     
  49.     int res[5] = {0,0,0,0,0};    
  50.     int n = 5; //物品的个数     
  51.     int c = 10; //背包能容的重量     
  52.     int i,j;    
  53.     package0_1(w,v,n,c);    
  54.     for(i=0;i<=n;i++)    
  55.     {    
  56.         for(j=0;j<=c;j++)    
  57.             printf("%2d ",f[i][j]);    
  58.         printf("\n");    
  59.     }    
  60.     getResult(n,c,res,v,w);    
  61.     printf("放入背包的物品为: \n");    
  62.     for(i=1;i<=n;i++)    
  63.         if(res[i] >= 1)    
  64.             printf("放入了第%d号物品%d个\n  ",i,res[i]);    
  65. }    


 

部分背包问题

与0-1背包的区别：装入的可以不是整个装入，理解为“装沙”。其余要求一样。

用贪心法求解

[cpp] view plaincopy
  1. #include<stdio.h>     
  2.   
  3. void package_part(int *w,int *v,double *p,int n,int c,int *flag)    
  4. {    
  5.     int i,j,temp;  
  6.     double tempD,totalValue = 0.0;  
  7.       
  8.     //计算单价  
  9.     for(i=0;i<n;i++)  
  10.     {  
  11.         p[i] = (double)v[i] / (double)w[i];  
  12.         flag[i] = i;  
  13.     }  
  14.     //根据单价排序,flag数组保存物品的下标  
  15.     for(i=0;i<n;i++)  
  16.     {  
  17.         for(j=n-1;j>i;j--)  
  18.         {  
  19.             if(p[j] > p[j-1])  
  20.             {  
  21.                 temp = flag[j];  
  22.                 flag[j] = flag[j-1];  
  23.                 flag[j-1] = temp;     
  24.                   
  25.                 tempD = p[j];  
  26.                 p[j] = p[j-1];  
  27.                 p[j-1] = tempD;  
  28.             }  
  29.         }  
  30.     }  
  31.     //贪心法得出应该装入的物品    
  32.     for(i=0;i<n;i++)  
  33.     {  
  34.         if(c >= w[flag[i]])  
  35.         {  
  36.             totalValue += v[flag[i]];  
  37.             c -= w[flag[i]];  
  38.             printf("第%d号物品整个放入\n",flag[i]);  
  39.         }else  
  40.         {  
  41.             totalValue += p[flag[i]] * (double)c / (double) w[flag[i]];  
  42.             printf("第%d号物品放入了%f\n",flag[i],(double)c / (double) w[flag[i]]);  
  43.             break;  
  44.         }  
  45.     }  
  46.     printf("总价值为:%f",totalValue);  
  47. }    
  48.   
  49. void main()    
  50. {    
  51.     int w[5] = {4,6,6,3,6};//每个物品的重量     
  52.     int v[5] = {1,1,1,2,1};//每个物品的价值     
  53.     double p[5] = {0,0,0,0,0};//每个物品的单位价值    
  54.     int flag[5]; //用于排序  
  55.     int n = 5; //物品的个数     
  56.     int c = 10; //背包能容的重量     
  57.     package_part(w,v,p,n,c,flag);    
  58. }    

 

郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。

标签： 编程语言 Java C C# Javascript js Python Ruby Spring 程序 VB

相关文章

随机文章

您可能还喜欢

您可能还喜欢