问题:实现从N个物品种找出价值总和最大的物品,放在额定容量的背包里。
#include <stdio.h>
#define N 100
int num_type;
int currentoption[N];
int option[N];
double maxvalue;/*最大值*/
double totalvalue;/*总价值*/
double limitweight;/*重量限制*/
struct
{
double weight;
double value;
}good[N];
void outchick(int i, double tw, double totalvalue)
{
int k;
if (tw + good[i].weight <= limitweight)
{
currentoption[i] = 1;
if (i < num_type - 1)
outchick(i + 1, tw + good[i].weight, totalvalue);
else
{
for (k = 0; k < num_type; ++k)
option[k] = currentoption[k];
maxvalue = totalvalue;
}
}
currentoption[i] = 0;
if (totalvalue - good[i].value > maxvalue)
{
if (i < num_type - 1)
outchick(i + 1, tw, totalvalue - good[i].value);
else
{
for (k = 0; k < num_type; ++k)
option[k] = currentoption[k];
maxvalue = totalvalue - good[i].value;
}
}
}
void main()
{
int i;
double weight, value;
printf("请输入物品的类别数:\n");
scanf_s("%d", &num_type);
printf("请输入物品的重量和价格\n");
totalvalue = 0.0;
for (i = 0; i < num_type; ++i)
{
scanf_s("%lf %lf", &weight, &value);
good[i].weight = weight;
good[i].value = value;
totalvalue += value;
}
printf("输入重量限制\n");
scanf_s("%lf", &limitweight);
limitweight = 0.0;
for (i = 0; i < num_type;++i)
{
currentoption[i] = 0;
}
outchick(0, 0.0, totalvalue);
for (i = 0; i < num_type;++i)
if (option[i])
printf("%d\t", i + 1);
printf("总价值是%2f", maxvalue);
}
scanf_s("%lf", &limitweight);
limitweight = 0.0;
你这里刚输入重量限制,又把它清掉干什么?