我在试着解分数背包,我的代码是:
#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);
}
字符串
当我输入profit = 10,weight = 3时,sort
函数的输出将pw_ratio
打印为3.000
(而不是3.333
),但是下一个迭代项(即第二项)给出了完美的十进制值。
我试着调试,当我在main
函数本身中打印pw_ratio
时(我正在为profit
和weight
输入),它是绝对正确的,即10/3将给予3.33,20/9将给出2.222等等。这里的问题是什么,如何解决?
3条答案
按热度按时间n6lpvg4x1#
在
int temp = a[i].pw_ratio;
中,您将比率存储在int
变量中,有效地截断了它。当您稍后执行a[j].pw_ratio = temp;
时,原始值不会恢复。整个交换过程可以通过一次交换整个
struct item
来简化,这样就可以在任何地方使用正确的类型。字符串
gxwragnw2#
您的排序函数使用
temp
(一个int
变量)在交换时临时存储值。这会导致某些值被截断为int
。你也不交换index
,尽管不清楚这是错误还是故意的。注意,可以使用标准库函数
qsort
对数组进行排序。除了更正确和更少的代码之外,当你的数组变长时,它会更有效。t0ybt7op3#
sort
函数使用一个int
变量来执行值交换,导致将double
值转换为int
,这有效地截断了这些值。在排序之后,您只需交换结构并重新构造index
成员。还请注意,您的排序方法不起作用:你应该只比较索引值为
i
和j
的元素,使得i < j
。以下是修改后的版本:
字符串
您也可以使用
<stdlib.h>
中定义的qsort
:型