我在试着解分数背包,我的代码是:

#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时(我在这里接受profitweight的输入),它是绝对正确的,即10/3将得到3.33%,20/9将得到2.222,依此类推.这里的问题是什么,如何解决这个问题?

推荐答案

int temp = a[i].pw_ratio;中,您将比率存储在int变量中,从而有效地截断它.以后执行a[j].pw_ratio = temp;操作时,不会恢复原始值.

整个交换过程可以通过一次交换全部struct item个来简化,然后将在所有地方使用正确的类型.

if (a[i].pw_ratio > a[j].pw_ratio) {
    struct item temp = a[i];
    a[i] = a[j];
    a[j] = temp;

    // swap back index
    int idx = a[i].index;
    a[i].index = a[j].index;
    a[j].index = idx;
}

C++相关问答推荐

传递给空闲的无效地址0x71 db7 cb5e0:未分配值

数组元素的编号索引

在32位处理器上优化53—32位模计算>

丑陋的三重间接:可扩展的缓冲区管理 struct

使用额外的公共参数自定义printf

Clang警告称,`ffi_type`与`sizeof`不兼容

如何确保在C程序中将包含uft8字符的字符串正确写入MySQL?

如何在提取的索引中分配空值?

如何只获取字符串的第一个单词,然后将其与c中的另一个单词进行比较?

如何在C++中安全地进行浮点运算

预处理器宏扩展(ISO/IEC 9899:1999(E)§;6.10.3.5示例3)

C:如何将此代码转换为与数组一起使用?

我可以创建适用于不同endian的 colored颜色 struct 吗?

Valgrind用net_pton()抱怨

按字典顺序打印具有给定字符的所有可能字符串

将不同类型的指针传递给函数(C)

使用替代日历打印日期

在 C/C++ 中原子按位与字节的最佳方法?

C 中 struct 体自赋值是否安全?特别是如果一侧是指向 struct 的指针?

如何让 unlinkat(dir_fd, ".", AT_REMOVEDIR) 工作?