#include <stdbool.h> #include <stdio.h> #include <stdlib.h> typedef struct {     int idx;  // インデックス。i = 1, 2, 3, 4     int v;    // 価値     int w;    // 重さ     double e; // v/w。評価値     bool on;  // 袋に入れるときtrue } Item; int cmp_idx(const void* a, const void* b) {     int a1 = ((const Item*)a)->idx;     int b1 = ((const Item*)b)->idx;     if (a1 < b1) return -1;     if (a1 > b1) return 1;     return 0; } int cmp_e(const void* a, const void* b) {     double a1 = ((const Item*)a)->e;     double b1 = ((const Item*)b)->e;     if (a1 < b1) return  1; // 降順なので     if (a1 > b1) return -1; // 逆にする     return 0; } void dsp_items(const Item a[], size_t sz) {     printf("idx   v   w      e on\n");     printf("---------------------\n");     for (size_t i = 0; i < sz; ++i)         printf("%3d %3d %3d %6.2f %2d\n"         , a[i].idx, a[i].v, a[i].w, a[i].e, a[i].on);     printf("\n"); } void dsp_on(const Item a[], size_t sz) {     for (size_t i = 0; i < sz; ++i)         printf("%sx%d = %d", i ? ", " : "", a[i].idx, a[i].on);     printf("\n"); } void solv(Item a[], size_t sz, int wmax) {     int wc = 0;     for (size_t i = 0; i < sz; ++i)         a[i].e = (double)a[i].v / a[i].w;     qsort(a, sz, sizeof(Item), cmp_e);     for (size_t i = 0; i < sz; ++i) {         int wt = wc + a[i].w;         if (wt <= wmax) {             a[i].on = true;             wc = wt;         } else             a[i].on = false;     }     dsp_items(a, sz);     qsort(a, sz, sizeof(Item), cmp_idx); } int main(void) {     Item a[] = {         {1, 2, 3, 0.0, false},         {2, 1, 1, 0.0, false},         {3, 8, 5, 0.0, false},         {4, 7, 4, 0.0, false}     };     const size_t sz = sizeof a/sizeof *a;     solv(a, sz, 6);     dsp_on(a, sz); } // 実行結果 idx   v   w      e on ---------------------   4   7   4   1.75  1   3   8   5   1.60  0   2   1   1   1.00  1   1   2   3   0.67  0 x1 = 0, x2 = 1, x3 = 0, x4 = 1