|
日历
| | 日 | 一 | 二 | 三 | 四 | 五 | 六 |
|---|
| 31 | 1 | 2 | 3 | 4 | 5 | 6 | | 7 | 8 | 9 | 10 | 11 | 12 | 13 | | 14 | 15 | 16 | 17 | 18 | 19 | 20 | | 21 | 22 | 23 | 24 | 25 | 26 | 27 | | 28 | 29 | 30 | 1 | 2 | 3 | 4 | | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
|
统计
- 随笔 - 1
- 文章 - 2
- 评论 - 0
- 引用 - 0
导航
常用链接
留言簿
随笔档案
文章档案
搜索
最新评论
|
 #include <stdio.h>
#include <tchar.h>
#include <time.h>
#include <stdlib.h>
#include <iostream>
#define p_n 30
#define p_c 10000
using namespace std;
void sortbyVW(int *sn_v,int *sn_w)
   {
 for(int j=0;j<p_n;j++)
  {
int v_temp=0;
int w_temp=0;
for(int i=0;i<p_n-j-1;i++)
if(float(sn_v[i]/sn_w[i])<=float(sn_v[i+1]/sn_w[i+1]))
{
v_temp=sn_v[i];
sn_v[i]=sn_v[i+1];
sn_v[i+1]=v_temp;
w_temp=sn_w[i];
sn_w[i]=sn_w[i+1];
sn_w[i+1]=w_temp;
 }
}
 }
float KNAPSACK(int n, float c, int *v, int *w,float *x) {
int i;
float nowvalue=0;
for(i=0; i<n; i++)
x[i]=0.0;
float cu=c;
for(i=0; i<n; i++)
{
if(w[i]<cu)
x[i]=1.0;
else
{
x[i]=cu/w[i];
for(;i<n-1;i++)
x[i+1]=0;
}
cu= cu-w[i]*x[i];
nowvalue+=x[i]*w[i]*v[i];
}
for(i=0;i<p_n;i++)
{
if(i%9==0)
printf("\n");
printf("%f ",x[i]);
}
printf("\n");
return nowvalue;
}
int main()
{
clock_t start,end;
int value[p_n],weight[p_n];
float nv,p_x[p_n];
int i;
start = clock();
srand(int(time(NULL)));
for(i=0;i <p_n; i++)
weight[i] =((( rand()%2000)+1));
srand(int(time(NULL)));
for(i=0;i<p_n;i++)
value[i]=((rand()%3000)+1);
printf("随机出来的重量各是：");
for(i=0;i<p_n;i++)
{
if(i%10==0)
printf("\n");
printf(" %d",weight[i]);
}
printf("\n随机出来的价格各是：");
for(i=0;i<p_n;i++)
{
if(i%10==0)
printf("\n");
printf(" %d ",value[i]);
}
sortbyVW(value,weight);
printf("\n随机出来的重量排序后各是：");
for(i=0;i<p_n;i++)
{
if(i%10==0)
printf("\n");
printf(" %d ",weight[i]);
}
printf("\n随机出来的价格排序后各是：");
for(i=0;i<p_n;i++)
{
if(i%10==0)
printf("\n");
printf(" %d",value[i]);
}
nv=KNAPSACK(p_n, p_c, value, weight, p_x);
end=clock();
printf("%d ,%d, %d, %f\n", p_n,p_c, (end-start),nv);
getchar();
return 0;
}
|