0-1背包问题（贪心算法）

野性酷女 2023-02-13 05:42 49阅读 0赞

## 0-1背包问题（贪心算法） ##

实验代码：

#include<stdio.h> 
    int max(int a,int b) 
    {
         
     if(a>b) 
      return a; 
     else 
      return b; 
    } 
    void Knapsack(int *v,int *w,int *x,int c,int n, int m[8][100]) 
    {
         
     int i,j; 
     for(j=0;j<c;j++) 
     {
         
      if(j<w[n])         
       m[n][j]=0; 
      else              
       m[n][j]=v[n]; 
     } 
     for(i=n-1;i>=1;i--) 
     {
         
      for(j=w[i];j<=c;j++)                   
       m[i][j]=max(m[i+1][j],m[i+1][j-w[i]]+v[i]);  } 
     for(i=1;i<n;i++)   
     {
         
      if(m[i][c]==m[i+1][c]) 
        x[i]=0; 
      else 
      {
        x[i]=1;   c=c-w[i];} 
     } 
     x[n]=(m[n][c])?1:0; 
     return; 
    } 
    
    int main() 
    {
         
     int i=0;
     int n=7; 
     int w[]={
        0,2,3,5,7,1,4,1}; 
     int v[]={
        0,10,5,15,7,6,18,3}; 
     int x[]={
        0,0,0,0,0,0,0,0}; 
     printf("物品总数为：7\n");
     printf("物品重量和价值分别为：\n");
     printf("\n重量    价值 \n"); 
     for (i=1;i<=n;i++) 
     printf("%d        %d \n",w[i],v[i]); 
     int m=15; 
     int array[8][100]={
        0}; 
     Knapsack(v,w,x,m,7,array); 
     printf("背包能装的最大价值为: %d\n",array[1][m]);
     printf("贪心算法的解为: "); 
     for(i=1;i<=n;i++) 
     {
         
      if(i==1) 
       printf("%d",x[i]); 
      else 
       printf("  %d",x[i]); 
     }  
     printf("\n"); 
     return 0;    
    }

运行结果：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1dYX3RpbWk_size_16_color_FFFFFF_t_70]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1dYX3RpbWk_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200527164206791.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1dYX3RpbWk=,size_16,color_FFFFFF,t_70