0-1リュックサックとリュックサックの問題(C言語実現)——欲張りアルゴリズム応用(3)

問題の説明:
n種類の品物とリュックサックを与えます.物品iの重量はw[i]であり、その価値はv[i]であり、リュックサックの容量はcである.リュックサックに入ったものの総価値が最大になるように、リュックサックに入ったものをどのように選択すればいいですか.各品物は最大1回まで入れます.
          
0-1リュックサックの問題:リュックサックに入れるものには、全部入れるか入れないかの2つの選択肢しかありません.
リュックサックの問題:リュックサックに入れるものについては、一部を入れることができますが、必ずしもリュックサックに全部入れる必要はありません.
アルゴリズム解析:
貪欲な戦略を用いてこのような問題を解く場合,まず最適なメトリック基準を選択しなければならない.
選択可能なメトリック基準は、価値、容量、単位価値(v/w、価値/重量)の3つです.
明らかに、価値の高い物品の容量は大きすぎるかもしれないし、容量の大きい物品の価値も低いかもしれない.最適なメトリック基準は単位価値です.
リュックサック問題アルゴリズムの考え方:
1、各物品を単位価値によって高いものから低いものに並べ替える.
2、最も価値の高い者はリュックサックに入れる.
3、リュックサックの余剰スペースを計算する.
4、リュックの残容量=0または荷物が全部リュックに入るまで2-3歩繰り返す(0-1リュックについては、リュックの残容量がいずれかの荷物または荷物が全部リュックに入れられないことを条件とする).
以下はC言語実装(DEV c++4.9.9.2実行通過)

#include

void package(int n,float c,float v[],float w[],float x[]);
void package0_1(int n,float c,float v[],float w[],float x[]); 

int main(void)
{
    int n = 3;
    float c = 20;
    float v[] = {24,15,25};
    float w[] = {15,10,18};//            
    float *x;
    x = (float*)malloc(sizeof(float)*n); 
    printf("******  *******
");
    package(n,c,v,w,x);
    printf("*******0-1  ******
");
    package0_1(n,c,v,w,x);
    system("PAUSE");

}

/*
*       
*  n:     
*  c：     
*  v[]:        
*  w[]:       （               ） 
*  x[]:        （0    ，1      ，0-1     ） 
*/
void package(int n,float c,float v[],float w[],float x[])
{
     int i;
     for(i=0;i c)
       {
         break;
       }
       
       x[i] = 1;
       c = c - w[i];
       printf("   %d   ，      %f.
",(i+1),c);
     }
     
     if(i<=n)//              
     {
        x[i] = c/w[i]; 
        
        printf("   %d    %f  .       0.
",(i+1),w[i]*x[i]);
     }     
}

/*
*  0-1     
*  n:     
*  c：     
*  v[]:        
*  w[]:       （               ） 
*  x[]:        （0    ，1      ） 
*/
void package0_1(int n,float c,float v[],float w[],float x[])
{
     int i;
     for(i=0;i c)
       {
         break;
       }
       
       x[i] = 1;
       c = c - w[i];
       printf("   %d   ，      %f.
",(i+1),c);
     }
}

 

リュックサック問題と0-1リュックサックはいずれも最適サブ構造の性質を持っているが、リュックサック問題は貪欲アルゴリズムで求められるのが最適解であり、0-1リュックサック問題は貪欲アルゴリズムによって最適解が得られない.最後にリュックサックをいっぱい入れることが保証できないため、一部の空きリュックサック空間は総価値を低下させた.