algorithms/data-structures/struct/struct_sort.c at main · microwind/algorithms · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
/**
 * Copyright © https://github.com/microwind All rights reserved.
 * @author: jarryli@gmail.com
 * @version: 1.0
 * @description: 结构体排序 - 贪心算法购书问题 - C实现
 */

#include <stdio.h>
#include <stdlib.h>

int TOTAL_MONEY = 1000;

struct Book
{
  int id;
  char title[50];
  double price;
  int count;
};

struct Book books[] = {
    {1, "语文", 4.0, 33},
    {2, "英语", 2.5, 45},
    {3, "数学", 6.6, 26},
    {4, "物理", 3.7, 83},
    {5, "化学", 5.2, 51},
    {6, "历史", 4.1, 63},
    {7, "化学", 3.7, 15},
    {8, "政治", 2.3, 76},
    {9, "生物", 4.8, 62},
    {10, "音乐", 6.2, 34}};

int isOverTotal(int number)
{
  return TOTAL_MONEY < number;
}

void insertSort(struct Book books[], int len)
{
  for (int i = 0; i < len; i++)
  {
    int j = i;
    struct Book current = books[i];
    while (j-- > 0 && current.price < books[j].price)
    {
      books[j + 1] = books[j];
    }
    books[j + 1] = current;
  }
}

void printBooks(struct Book books[], int len)
{
  printf("顺序 原序号 名称 价格 数量\n");
  for (int i = 0; i < len; i++)
  {
    printf("%d)   %d     %s  %.1f  %d\n", i, books[i].id, books[i].title, books[i].price, books[i].count);
  }
}

int main()
{
  int booksLen = sizeof(books) / sizeof(books[0]);
  printf("使用插入排序 \n");
  insertSort(books, booksLen);

  printf("按价格排序后:\n");
  printBooks(books, booksLen);

  int buyCount = 0;
  int currentCost = 0;
  printf("== 开始购买计算 ==:\n");
  for (int i = 0; i < booksLen; i++)
  {
    struct Book book = books[i];
    currentCost += book.price * book.count;
    buyCount += book.count;
    printf("%d) 购买了: %d本%s, 单价:%.2f。", i + 1, book.count, book.title, book.price);
    printf("%s %d %s %d\n", " 当前购买总数：", buyCount, " 总花费：", currentCost);
    if (isOverTotal(currentCost))
    {
      printf("购买到 %s 时超出了金额。需要从最近购买项里面逐个移除以符合预算。\n", book.title);

      for (int j = 0; j < book.count; j++)
      {
        currentCost -= book.price;
        printf("\n减掉1本%s, 减去%.1f", book.title, book.price);
        buyCount--;
        if (!(isOverTotal(currentCost)))
        {
          printf("\n符合金额要求了, %s 只能买 %d 本。\n", book.title, book.count - j);
          break;
        }
      }

      break;
    }
  }
  printf("%s %d %s %d\n", "您最大购买总数：", buyCount, " 总花费：", currentCost);
}

/**
jarry@jarrys-mbp struct % gcc struct_sort.c
jarry@jarrys-mbp struct % ./a.out
使用插入排序
按价格排序后:
顺序 原序号 名称 价格 数量
0)   8     政治  2.3  76
1)   2     英语  2.5  45
2)   4     物理  3.7  83
3)   7     化学  3.7  15
4)   1     语文  4.0  33
5)   6     历史  4.1  63
6)   9     生物  4.8  62
7)   5     化学  5.2  51
8)   10     音乐  6.2  34
9)   3     数学  6.6  26
== 开始购买计算 ==:
1) 购买了: 76本政治, 单价:2.30。 当前购买总数： 76  总花费： 174
2) 购买了: 45本英语, 单价:2.50。 当前购买总数： 121  总花费： 286
3) 购买了: 83本物理, 单价:3.70。 当前购买总数： 204  总花费： 593
4) 购买了: 15本化学, 单价:3.70。 当前购买总数： 219  总花费： 648
5) 购买了: 33本语文, 单价:4.00。 当前购买总数： 252  总花费： 780
6) 购买了: 63本历史, 单价:4.10。 当前购买总数： 315  总花费： 1038
购买到 历史 时超出了金额。需要从最近购买项里面逐个移除以符合预算。

减掉1本历史, 减去4.1
减掉1本历史, 减去4.1
减掉1本历史, 减去4.1
减掉1本历史, 减去4.1
减掉1本历史, 减去4.1
减掉1本历史, 减去4.1
减掉1本历史, 减去4.1
减掉1本历史, 减去4.1
符合金额要求了, 历史 只能买 56 本。
您最大购买总数： 307  总花费： 998
*/