Question

0-1背包的c语言程序运行结果总是出错，求指教

测试数据：
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;
}

Answer 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背包问题的动态规划还是有点难理解的。

追问

我用成贪心算法了~~~

Answer 2

学妹。。。
算法实习又遇到难题了？？？给你个链接，好多背包问题的讲解哦
http://wenku.baidu.com/view/e97568d6b9f3f90f76c61b7d.html