欧美性猛交XXXX免费看蜜桃,成人网18免费韩国,亚洲国产成人精品区综合,欧美日韩一区二区三区高清不卡,亚洲综合一区二区精品久久

#define N 4 /*物品個(gè)數*/
#define W 5/*背包容量*/
#include <stdio.h>

/*******************************************************************
*************以下為動(dòng)態(tài)規劃算法解0-1背包問(wèn)題****************/
int min(int a,int b)
{
return (a<b) ? a : b;
}
float max(float a,float b)
{
return (a>b) ? a : b;
}
void Knap(float*v,int *w,int c,float m[N+1][W+1])
{
int i,j;
int jMax=min(w[N]-1,c);
for(j=0;j<=jMax;j++) m[N][j]=0;
for(j=w[N];j<=c;j++) m[N][j]=v[N];
for(i=N-1;i>1;i--)
{
  jMax=min(w[i]-1,c);
  for(j=0;j<=jMax;j++) m[i][j]=m[i+1][j];
  for(j=w[i];j<=c;j++) m[i][j]=max(m[i+1][j],m[i+1][j-w[i]]+v[i]);
}
m[1][c]=m[2][c];
if(c>=w[1]) m[1][c]=max(m[1][c],m[2][c-w[1]]+v[1]);
}
void Traceback(float m[N+1][W+1],int *w,int c,int *x)
{
int i;
for(i=1;i<N;i++)
  if(m[i][c]==m[i+1][c]) x[i]=0;
  else {x[i]=1; c-=w[i];}
x[N]=( (m[N][c]) ? 1 : 0 );
}
void Knapsack_1(float*v,int *w,int c,float m[N+1][W+1],int *x)
{
Knap(v,w, c,m);
Traceback(m,w,c,x);
}

/*******************************************************************
*****************以下為貪心算法解背包問(wèn)題*********************/
void sort(float *v,float *w)
{
int i,j;
float temp;
for(i=1;i<N;i++)
  for(j=i+1;j<=N;j++)
   if(v[i]/w[i]<v[j]/w[j])
   {
    temp=v[i]; v[i]=v[j]; v[j]=temp;
    temp=w[i]; w[i]=w[j]; w[j]=temp;
   }
}
void Knapsack_2(float c,float *v,float *w,float *y)
{
int i;
sort(v,w);
for(i=1;i<=N;i++) y[i]=0;
for(i=1;i<=N;i++)
{
  if(w[i]>c) break;
  y[i]=1;
  c-=w[i];
}
if(i<=N)
  y[i]=c/w[i];
}

/*******************************************************************
*************************以下為主函數***************************/
main()
{
float m[N+1][W+1] , v[N+1]={N,1,2,2,1} , w_2[N+1]={N,2,1,2,3} , c_2=W;/*v[]存儲價(jià)值，w[]存儲質(zhì)量，c為背包容量*/
int w_1[N+1]={N,2,1,2,3},c_1=W;
float y[N+1];
int x[N+1];
int i,j;
float vSum=0,wSum=0;
Knapsack_1(v,w_1,c_1,m,x);
printf("利用線(xiàn)性規劃算法后，背包中的物品價(jià)值和質(zhì)量為：\n");
j=0;
for(i=1;i<=N;i++)
  if(x[i])
  {
   printf("物品%d的價(jià)值為%g、質(zhì)量為%d\n",++j,v[i],w_1[i]);
   vSum+=v[i]; wSum+=w_1[i];
  }
printf("背包中總價(jià)值為%g、總質(zhì)量為%g、背包剩余容量為%g\n",vSum,wSum,c_1-wSum);

Knapsack_2(c_2,v,w_2,y);
vSum=wSum=0;
j=0;
printf("\n利用貪心算法后，背包中的物品價(jià)值和質(zhì)量為：\n");
for(i=1;i<=N;i++)
  if(y[i])
  {
   printf("物品%d的價(jià)值為%g、質(zhì)量為%g\n",++j,v[i]*y[i],w_2[i]*y[i]);
   vSum+=v[i]*y[i]; wSum+=w_2[i]*y[i];
  }
printf("背包中總價(jià)值為%g、總質(zhì)量為%g、背包剩余容量為%g\n",vSum,wSum,c_2-wSum);

printf("\n注：兩個(gè)算法得出的結果不一定相同，這是正常的。\n");
}