我在试着解分数背包,我的代码是:
#include <stdio.h>
struct item {
int index;
double profit;
double weight;
double pw_ratio;
};
void sort(struct item a[], int n) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (a[i].pw_ratio > a[j].pw_ratio) {
int temp = a[i].pw_ratio;
a[i].pw_ratio = a[j].pw_ratio;
a[j].pw_ratio = temp;
temp = a[i].profit;
a[i].profit = a[j].profit;
a[j].profit = temp;
temp = a[i].weight;
a[i].weight = a[j].weight;
a[j].weight = temp;
}
}
}
printf("Sorted items: \n");
for (int i = 0; i < n; i++) {
printf("%d\t%lf\t%lf\t%lf\n", a[i].index, a[i].pw_ratio,
a[i].profit, a[i].weight);
}
}
int main() {
int n;
printf("Enter the number of items: ");
scanf("%d", &n);
int capacity;
printf("Enter the capacity of knapsack: ");
scanf("%d", &capacity);
struct item a[n];
for (int i = 0; i < n; i++) {
a[i].index = i + 1;
printf("Enter profit of item%d: ", i + 1);
scanf("%lf", &a[i].profit);
printf("Enter weight of item%d: ", i + 1);
scanf("%lf", &a[i].weight);
a[i].pw_ratio = (double)a[i].profit / a[i].weight;
//printf("Profit-weight ratio: %lf", a[i].pw_ratio);
}
sort(a, n);
//solve(a, n);
}
当输入利润=10,权重=3时,sort
函数的输出将pw_ratio
打印为3.000
(而不是3.333
),但是下一迭代项(即第二项)给出的是完美的小数值.
我试过调试,当我在main
函数本身中打印pw_ratio
时(我在这里接受profit
和weight
的输入),它是绝对正确的,即10/3将得到3.33%,20/9将得到2.222,依此类推.这里的问题是什么,如何解决这个问题?