0-1背包的c语言程序运行结果总是出错,求指教
测试数据:102312112322342897792522102101004566778911457911121314151721890100标准输出:014912193...
测试数据:
1 0
2
3
1 2
1
1
2 3
2 2
3 4
2 8
9 7
7 9
2 5
2 2
10 2
10 100
4 5 6 6 7 7 8 9 11 45
7 9 11 12 13 14 15 17 21 89
0 1
0 0
标准输出:0
1
4
9
12
193
0
我的输出:
0
1
5
9
12
193
0
不知道为什么那个数据会出错
源代码如下:
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
int n=0; //n 个物品
int c=0; //容量为c 的背包
int cw; //当前重量
int cp=0; //当前价值
int bestp=0;//当前最有价值
struct Goods
{
float wi;//每件物品i的重量为wi
float pi;//价值为pi
float averpi; //单位价值
float state;
};
void AverPi(struct Goods goods[])
{
int i;
for(i=0; i<n; i++)
{
goods[i].averpi= goods[i].pi/goods[i].wi;
}
}
void Sort(struct Goods goods[])
{
int i,j;
double temp1,temp2,temp3;
for(i=0; i<=n-1 ; i++)
{
for(j=0; j<n-i; j++)
{
if(goods[j].averpi<goods[j+1].averpi)
{
temp1 = goods[j].averpi;
goods[j].averpi = goods[j+1].averpi;
goods[j+1].averpi = temp1;
temp2 = goods[j].wi;
goods[j].wi = goods[j+1].wi;
goods[j+1].wi = temp2;
temp3 = goods[j].pi;
goods[j].pi = goods[j+1].pi;
goods[j+1].pi = temp3;
}
}
}
}
void Print(struct Goods goods[])
{
int i;
for(i=0; i<n; i++)
{
printf("%f****%f****%f****%f\n",goods[i].wi,goods[i].pi,goods[i].averpi,goods[i].state);
}
}
void Bestw(struct Goods goods[]) //求最优值
{
int i;
float bestp=0;
for(i=0; i<n ; i++)
{
bestp += goods[i].wi;
if(bestp < c)
{
goods[i].state = 1;
}
else
{
bestp -= goods[i].wi;
goods[i].state = (c-bestp)/goods[i].wi;
break;
}
}
}
int Bestp(struct Goods goods[])
{
int i;
float bestw = 0.0;
for(i=0; i<n ;i++)
{
if(goods[i].state != 0.0)
{
bestw += goods[i].state * goods[i].pi;
}
}
return bestw;
}
int main(void)
{
int i;
scanf("%d %d",&n,&c);
while(n != 0||c != 0)
{
struct Goods goods[n];
for(i=0; i<n ; i++)
{
scanf("%f",&goods[i].wi);
goods[i].state = 0;
}
for(i=0; i<n ; i++)
{
scanf("%f",&goods[i].pi);
goods[i].state = 0;
}
AverPi(goods);
Sort(goods);
//Print(goods);
Bestw(goods);
// Print(goods);
printf("%d\n",Bestp(goods));
scanf("%d %d",&n,&c);
}
return 0;
} 展开
1 0
2
3
1 2
1
1
2 3
2 2
3 4
2 8
9 7
7 9
2 5
2 2
10 2
10 100
4 5 6 6 7 7 8 9 11 45
7 9 11 12 13 14 15 17 21 89
0 1
0 0
标准输出:0
1
4
9
12
193
0
我的输出:
0
1
5
9
12
193
0
不知道为什么那个数据会出错
源代码如下:
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
int n=0; //n 个物品
int c=0; //容量为c 的背包
int cw; //当前重量
int cp=0; //当前价值
int bestp=0;//当前最有价值
struct Goods
{
float wi;//每件物品i的重量为wi
float pi;//价值为pi
float averpi; //单位价值
float state;
};
void AverPi(struct Goods goods[])
{
int i;
for(i=0; i<n; i++)
{
goods[i].averpi= goods[i].pi/goods[i].wi;
}
}
void Sort(struct Goods goods[])
{
int i,j;
double temp1,temp2,temp3;
for(i=0; i<=n-1 ; i++)
{
for(j=0; j<n-i; j++)
{
if(goods[j].averpi<goods[j+1].averpi)
{
temp1 = goods[j].averpi;
goods[j].averpi = goods[j+1].averpi;
goods[j+1].averpi = temp1;
temp2 = goods[j].wi;
goods[j].wi = goods[j+1].wi;
goods[j+1].wi = temp2;
temp3 = goods[j].pi;
goods[j].pi = goods[j+1].pi;
goods[j+1].pi = temp3;
}
}
}
}
void Print(struct Goods goods[])
{
int i;
for(i=0; i<n; i++)
{
printf("%f****%f****%f****%f\n",goods[i].wi,goods[i].pi,goods[i].averpi,goods[i].state);
}
}
void Bestw(struct Goods goods[]) //求最优值
{
int i;
float bestp=0;
for(i=0; i<n ; i++)
{
bestp += goods[i].wi;
if(bestp < c)
{
goods[i].state = 1;
}
else
{
bestp -= goods[i].wi;
goods[i].state = (c-bestp)/goods[i].wi;
break;
}
}
}
int Bestp(struct Goods goods[])
{
int i;
float bestw = 0.0;
for(i=0; i<n ;i++)
{
if(goods[i].state != 0.0)
{
bestw += goods[i].state * goods[i].pi;
}
}
return bestw;
}
int main(void)
{
int i;
scanf("%d %d",&n,&c);
while(n != 0||c != 0)
{
struct Goods goods[n];
for(i=0; i<n ; i++)
{
scanf("%f",&goods[i].wi);
goods[i].state = 0;
}
for(i=0; i<n ; i++)
{
scanf("%f",&goods[i].pi);
goods[i].state = 0;
}
AverPi(goods);
Sort(goods);
//Print(goods);
Bestw(goods);
// Print(goods);
printf("%d\n",Bestp(goods));
scanf("%d %d",&n,&c);
}
return 0;
} 展开
2个回答
展开全部
你没理解什么是0 1背包问题,要么背要么不背不能切分你这是部分背包问题的程序。
可以分析你结果是5的树据
2 3
2 2
3 4
程序先算价值得出第二个价值大是2第一个价值只有1.5
然后程序选择第二个,然后还剩下1kg选择背第一个的1kg可是可怕的事情来了,你int型数 1*2=2
你背了第一个物品1kg的那部分价值竟然为2
然后结果自然就是2+3=5;
由此可见你如果改成float型就是比较正确的求部分背包问题了。
而0 1背包问题是用动态规划算法而不是你现在的贪心。实际上0 1背包问题的动态规划还是有点难理解的。
可以分析你结果是5的树据
2 3
2 2
3 4
程序先算价值得出第二个价值大是2第一个价值只有1.5
然后程序选择第二个,然后还剩下1kg选择背第一个的1kg可是可怕的事情来了,你int型数 1*2=2
你背了第一个物品1kg的那部分价值竟然为2
然后结果自然就是2+3=5;
由此可见你如果改成float型就是比较正确的求部分背包问题了。
而0 1背包问题是用动态规划算法而不是你现在的贪心。实际上0 1背包问题的动态规划还是有点难理解的。
追问
我用成贪心算法了~~~
已赞过
已踩过<
评论
收起
你对这个回答的评价是?
展开全部
本回答被提问者采纳
已赞过
已踩过<
评论
收起
你对这个回答的评价是?
推荐律师服务:
若未解决您的问题,请您详细描述您的问题,通过百度律临进行免费专业咨询