Программирование ScubaDiv, логическая ошибка с выводом

Question

Эта проблема касается дайвера или нескольких дайверов, которые должны принимать баллоны, которые содержат кислород и азот внутри, также баллон имеет собственный вес. Используя динамическое программирование, мы должны придумать решения, которые сообщают дайверу наилучший вес, который он может получить с нужными Oxy и Nitro (чтобы максимизировать время под водой для дайвера)

Ввод выглядит так:

1          //the number of divers
5 60       // ox=5 and ni=60 , the amonut of OX and NI the diver needs
5          //the number of cylinders to choose - n.
3 36 120   // 1st cyllinder => ox=3 / nit=36 / weight = 120
10 25 129  // 2nd cyllinder
5 50 250   // 3rd cyllinder
1 45 130   // 4th cyllinder
4 20 119   // 5th cyllinder

И вывод здесь должен выглядеть так:

249  //the tot weight
1 2  //cyllinders which were chosen (in this case 1st and 2nd cyllinder)

Я могу найти 249, так что вес, но я изо всех сил пытаюсь понять, как получить индексы цилиндров, может кто-нибудь дать мне подсказку или указать мне, как я могу этого достичь. Вот функция, которая вычисляет вес:

int ox,ni,n;
int o[1000],nit[1000],w[1000];

int best[22][80],next[22][80];

int solve()
    {
        memset(best, 0x3f, sizeof(best));
        best[0][0] = 0;
        for (int k = 0; k < n ;k++)
        {
           memcpy(next,best,sizeof(best));

           for (int i = 0; i <= ox ;i++)
           {
                for (int j = 0 ; j <= ni ;j++)
                {
                    next[min(ox,i+o[k])][min(ni,j+nit[k])]= min(best[i][j]+w[k], next[min(ox,i+o[k])][min(ni,j+nit[k])]);
                }
           }
           memcpy(best,next,sizeof(best));
        }
        cout << endl;

        return best[ox][ni];
    }

Я пытался сделать такое утверждение в третьем цикле for:

if (((next[min(ox,i+o[k])][min(ni,j+nit[k])]) == (best[i][j]+w[k])) && ((min(ox, i+o[k]) == ox) || (min(ni, j+nit[k])== ni) )) 
                    {
                        cout << k << " ";
                    }

Но это не работает в большинстве случаев. Кто-нибудь может дать мне подсказку или указать, как сделать заявление, чтобы поймать и напечатать правильные индексы цилиндров?

---

Новые обновленные изменения:

    #include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>
#include <iostream>

using namespace std;

typedef struct {    /* typedef for struct containing tank vals */
    int ox,
        nit,
        wt;
} tank_t;

int main() {

    int ndivers = 0,        /* number of divers */
    oxreq = 0,          /* minimum oxygen required */
    nitreq = 0,         /* minimum nitrogen required */
    n = 0,              /* number of cylinders actually read */
    ncyl = 0,           /* number of cylinders from input file */
    wtmin = INT_MAX,    /* minimum weight (initialize to INT_MAX) */
    *indexes = NULL;    /* pointer to track tank indexes */
    tank_t *tanks = NULL, best;   /* pointer to tanks struct */

    best.ox = 0;

    /* allocate/validate storage for ncyl integers */
    if ((indexes = (int*)calloc(ncyl, sizeof *indexes)) == NULL) {
        perror("calloc-indexes");
        return 1;
    }

    /* allocate/validate storage for ncyl tanks */
    if ((tanks = (tank_t*)calloc(ncyl, sizeof *tanks)) == NULL) {
        perror("calloc-tanks");
        return 1;
    }

    cin >> ndivers;

    for(int i=0; i<ndivers; i++)
    {
        cin >> oxreq >> nitreq;
        cin >> ncyl;
        n = ncyl;

        for (int i = 0; i < ncyl; i++)
        {
            cin >> tanks[i].ox >> tanks[i].nit >> tanks[i].wt;
        }
    }



    /* loop over each tank to use as beginning in calc */
    for (int i = 0; i < n; i++) {
        int j = i + 1,      /* set 2nd index as next tank */
            *idx =(int*) calloc(n, sizeof *idx); /* allocate/zero temp index */
                                           /* can move idx alloc out of loop & memset here */
        if (!idx) { /* validate allocation */
            perror("calloc-idx");
            return 1;
        }
        /* use a temp tank_t struct tmp to accumulate values */
        tank_t tmp = { tanks[i].ox, tanks[i].nit, tanks[i].wt };
        idx[i] = 1;                     /* set 1st index value in tmp index */
        while (j < n) {                 /* loop over remaining tanks */
        idx[j] = 1;                 /* set next index as used */
        tmp.ox += tanks[j].ox;      /* add next tank ox */
        tmp.nit += tanks[j].nit;    /* add next tank nit */
        tmp.wt += tanks[j].wt;      /* add next tank wt */
                                        /* check if total ox & nit meet min, & wt < current min */
            if (tmp.ox > oxreq && tmp.nit > nitreq && tmp.wt < wtmin) {
                best = tmp;             /* save ox, nit & wt in best */
                wtmin = tmp.wt;         /* update minimum wt */
                memcpy(indexes, idx, n * sizeof *idx); /* copy to indexes */
                memset(idx, 0, sizeof *idx * n);   /* re-zero idx */
                memset(&tmp, 0, sizeof tmp);   /* zero tmp tank */
                idx[i] = 1;                     /* set 1st tank index */
                tmp.ox = tanks[i].ox;   /* set 1st tank values */
                tmp.nit = tanks[i].nit;
                tmp.wt = tanks[i].wt;
            }
            j++;    /* increment 2nd tank counter */
        }
        free(idx); /* free temp index */
    }
    free(tanks);   /* free tanks data - done with it */

    cout << best.wt;

    for (int i = 0; i < n; i++)
    {
        if (indexes[i])
            cout << i + 1 << " ";
    }

    free(indexes); /* free final indexes */

    return 0;
}

Answer 1

Я не уверен, насколько вы продвинулись с предложением использовать struct для координации различных частей информации о танке, а не пытаться координировать индексы из трех отдельных массивов. Вот несколько мыслей и пример. Пример - лишь один из бесчисленных способов приблизиться к этому, и это был только мой первый способ суммирования информации о резервуаре, чтобы соответствовать минимальным ox и nit, требуемым при минимизации общего веса в целом.

Не было предпринято никаких попыток максимизировать ox или nit, если альтернативы весу танка обеспечивают одинаковый минимальный вес (что вам следует сделать)

Во-первых, как указано в комментарии, каждый раз, когда у вас есть несколько фрагментов информации, которую вам нужно координировать в одной единице данных, вы должны думать struct. В своем коде вы пытаетесь управлять своими данными с помощью:

int ox,ni,n;
int o[1000],nit[1000],w[1000];

int best[22][80],next[22][80];

Несмотря на то, что выполнимо, выделение фиксированного хранилища для проекта, который должен обрабатывать данные «динамически», просто кажется неправильным из слова «Go» (не говоря уже о путанице). Вместо этого используйте простой struct для ваших данных типа tank_type, например,

typedef struct {    /* typedef for struct containing tank vals */
    int ox,
        nit,
        wt;
} tank_t;

(и вы можете использовать typedef, чтобы избежать необходимости писать stuct ... все время)

Преимущество заключается в том, что теперь вы можете выделить хранилище для no. of cylinders структур и затем получить доступ к своим данным с помощью единого координированного индекса для всех значений резервуара, например,

    tank_t *tanks = NULL, ...;   /* pointer to tanks struct */
    ...
    /* validate number of cylinders read from file */
    if (fscanf (fp, "%d", &ncyl) != 1 || ncyl < 1) {
        fprintf (stderr, "error: read failed - no. of cylinders.\n");
        return 1;
    }
    ...
    /* allocate/validate storage for ncyl tanks */
    if ((tanks = calloc (ncyl, sizeof *tanks)) == NULL) {
        perror ("calloc-tanks");
        return 1;
    }

Теперь вы можете просто прочитать ваши данные в tanks[0].ox, tanks[0].nit, ... tanks[1].ox, tanks[1].nit, ....

Чтобы отслеживать индексы танков, просто выделите no. of cylinders int, и вы можете установить текущие индексы, которые вы сравниваете с 1, оставляя остаток как 0. (вы можете использовать аналогичный временный индекс для рабочих целей и назначить текущие минимальные индексы комбинации резервуаров, которые соответствуют вашим критериям, последнему блоку памяти, в котором будут храниться результаты ваших итераций) *

Остальная часть проблемы состоит в том, чтобы просто придумать логику для перебора всех комбинаций танков, сохранить вес каждой комбинации, которая соответствует вашим критериям ox и nit, и сравнить каждую такую ​​комбинацию с текущим минимумом, пока вы идти. Вам просто нужно убедиться, что при реализации вашей логики, которую вы отслеживаете, вы сбрасываете значения по мере необходимости, чтобы вы в итоге получили правильное сравнение.

(первая мысль, которая пришла в голову, была вложенным набором циклов, похожим на простую процедуру сортировки по массиву, которая будет перебирать, складывать и сравнивать различные комбинации. [Без сомнения, есть более эффективный способ сделать это ])

Ниже приведен результат, который служит примером для одного подхода (с дополнительными комментариями, чтобы помочь вам следовать). Также обратите внимание, что я только что прочитал ваш файл данных, как вы его опубликовали (включая комментарии), чтобы вы могли немного упростить процедуру чтения (если немного), если ваш фактический файл пропускает комментарии.

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

typedef struct {    /* typedef for struct containing tank vals */
    int ox,
        nit,
        wt;
} tank_t;

void empty_line (FILE *fp)  /* simple function to strip comments from */
{                           /* your input file */
    int c = fgetc (fp);

    while (c != '\n' && c != EOF)
        c = fgetc (fp);
}

int main (int argc, char **argv) {

    int ndivers = 0,        /* number of divers */
        oxreq = 0,          /* minimum oxygen required */
        nitreq = 0,         /* minimum nitrogen required */
        n = 0,              /* number of cylinders actually read */
        ncyl = 0,           /* number of cylinders from input file */
        wtmin = INT_MAX,    /* minimum weight (initialize to INT_MAX) */
        *indexes = NULL;    /* pointer to track tank indexes */
    tank_t *tanks = NULL, best = { .ox = 0 };   /* pointer to tanks struct */
    /* open file given as 1st argument or read from stdin */
    FILE *fp = argc > 1 ? fopen (argv[1], "r") : stdin;

    if (!fp) {  /* validate file open for reading */
        fprintf (stderr, "error: file open failed '%s'.\n", argv[1]);
        return 1;
    }

    /* validate number of divers read */
    if (fscanf (fp, "%d", &ndivers) != 1 || ndivers < 1) {
        fprintf (stderr, "error: read failed - number of divers.\n");
        return 1;
    }
    empty_line (fp);    /* strip remaining comments in line */

    /* validate required ox and nit read from file */
    if (fscanf (fp, "%d %d", &oxreq, &nitreq) != 2 || 
                oxreq < 1 || nitreq < 1) {
        fprintf (stderr, "error: read failed - ox, nit required.\n");
        return 1;
    }
    empty_line (fp);

    /* validate number of cylinders read from file */
    if (fscanf (fp, "%d", &ncyl) != 1 || ncyl < 1) {
        fprintf (stderr, "error: read failed - no. of cylinders.\n");
        return 1;
    }
    empty_line (fp);

    /* allocate/validate storage for ncyl integers */
    if ((indexes = calloc (ncyl, sizeof *indexes)) == NULL) {
        perror ("calloc-indexes");
        return 1;
    }

    /* allocate/validate storage for ncyl tanks */
    if ((tanks = calloc (ncyl, sizeof *tanks)) == NULL) {
        perror ("calloc-tanks");
        return 1;
    }

    /* read/validate tank information - store in tanks */
    while (n < ncyl && fscanf (fp, "%d %d %d", &tanks[n].ox, 
            &tanks[n].nit, &tanks[n].wt) == 3) {
        empty_line (fp);
        n++;
    }
    if (fp != stdin) fclose (fp);   /* close file if not stdin */

    /* loop over each tank to use as beginning in calc */
    for (int i = 0; i < n; i++) {
        int j = i + 1,      /* set 2nd index as next tank */
            *idx = calloc (n, sizeof *idx); /* allocate/zero temp index */
                            /* can move idx alloc out of loop & memset here */
        if (!idx) { /* validate allocation */
            perror ("calloc-idx");
            return 1;
        }
        /* use a temp tank_t struct tmp to accumulate values */
        tank_t tmp = { tanks[i].ox, tanks[i].nit, tanks[i].wt };
        idx[i] = 1;                     /* set 1st index value in tmp index */
        while (j < n) {                 /* loop over remaining tanks */
            idx[j] = 1;                 /* set next index as used */
            tmp.ox += tanks[j].ox;      /* add next tank ox */
            tmp.nit += tanks[j].nit;    /* add next tank nit */
            tmp.wt += tanks[j].wt;      /* add next tank wt */
            /* check if total ox & nit meet min, & wt < current min */
            if (tmp.ox > oxreq && tmp.nit > nitreq && tmp.wt < wtmin) {
                best = tmp;             /* save ox, nit & wt in best */
                wtmin = tmp.wt;         /* update minimum wt */
                memcpy (indexes, idx, n * sizeof *idx); /* copy to indexes */
                memset (idx, 0, sizeof *idx * n);   /* re-zero idx */
                memset (&tmp, 0, sizeof tmp);   /* zero tmp tank */
                idx[i] = 1;                     /* set 1st tank index */
                tmp.ox = tanks[i].ox;   /* set 1st tank values */
                tmp.nit = tanks[i].nit;
                tmp.wt = tanks[i].wt;
            }
            j++;    /* increment 2nd tank counter */
        }
        free (idx); /* free temp index */
    }
    free (tanks);   /* free tanks data - done with it */

    /* output results */
    printf ("best tank combo that meets: O2 >= %d, N >= %d\n\n"
            "  O2: %d\n  N : %d\n  wt: %d\n\n  tanks:",
            oxreq, nitreq, best.ox, best.nit, best.wt);
    for (int i = 0; i < n; i++)
        if (indexes[i])
            printf (" %d", i + 1);
    putchar ('\n');

    free (indexes); /* free final indexes */

    return 0;
}

Пример входного файла

$ cat dat/tank.txt
1          //the number of divers
5 60       // ox=5 and ni=60 , the amonut of OX and NI the diver needs
5          //the number of cylinders to choose - n.
3 36 120   // 1st cyllinder => ox=3 / nit=36 / weight = 120
10 25 129  // 2nd cyllinder
5 50 250   // 3rd cyllinder
1 45 130   // 4th cyllinder
4 20 119   // 5th cyllinder

Пример использования / Вывод

$ ./bin/tankopt <dat/tank.txt
best tank combo that meets: O2 >= 5, N >= 60

  O2: 13
  N : 61
  wt: 249

  tanks: 1 2

Использование памяти / проверка ошибок

В любом написанном вами коде, который динамически распределяет память, у вас есть 2 обязанностей относительно любого выделенного блока памяти: (1) всегда сохраняйте указатель на начальный адрес для блока памяти, таким образом, (2) он может быть освобожден , когда он больше не нужен.

Крайне важно, чтобы вы использовали программу проверки ошибок памяти, чтобы убедиться, что вы не пытаетесь получить доступ к памяти или писать за пределами / за пределами выделенного блока, пытаться прочитать или основать условный переход на неинициализированном значении и, наконец, , чтобы подтвердить, что вы освобождаете всю выделенную память.

Для Linux valgrind - нормальный выбор. Для каждой платформы есть похожие проверки памяти. Все они просты в использовании, просто запустите вашу программу через него.

$ valgrind ./bin/tankopt <dat/tank.txt
==6126== Memcheck, a memory error detector
==6126== Copyright (C) 2002-2015, and GNU GPL'd, by Julian Seward et al.
==6126== Using Valgrind-3.12.0 and LibVEX; rerun with -h for copyright info
==6126== Command: ./bin/tankopt
==6126==
best tank combo that meets: O2 >= 5, N >= 60

  O2: 13
  N : 61
  wt: 249

  tanks: 1 2
==6126==
==6126== HEAP SUMMARY:
==6126==     in use at exit: 0 bytes in 0 blocks
==6126==   total heap usage: 7 allocs, 7 frees, 180 bytes allocated
==6126==
==6126== All heap blocks were freed -- no leaks are possible
==6126==
==6126== For counts of detected and suppressed errors, rerun with: -v
==6126== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)

Всегда подтверждайте, что вы освободили всю выделенную память и что ошибок памяти нет.

Дайте мне знать, если у вас есть дополнительные вопросы. Этот пример, как указывалось ранее, должен был предоставить пример одного подхода для итераций и отслеживания индекса - он не предназначен, чтобы быть единственным способом сделать это (или наиболее эффективным)

---

Добавление подсказок и чтение из stdin

Если внимательно, код уже настроен для чтения из файла, если в качестве 1-го аргумента указано имя файла, - или - для чтения из stdin, если аргумент не задан. Это достигается использованием троичного оператора в объявлении FILE, например ::1010 *

FILE *fp = argc > 1 ? fopen (argv[1], "r") : stdin;

Тернарный оператор - это просто сокращение if-else, структурированное как (condition) ? value if true : value if false;. Таким образом, выше (argc > 1) ? fopen (argv[1], "r") : stdin; check равен argc > 1 и, если это так, открывает имя файла, указанное в argv[i], в противном случае он просто присваивает stdin fp.

Зная, что вы уже можете читать из stdin (и перемещая выделение idx вне цикла, как упомянуто в комментариях к коду выше), вы можете сделать что-то вроде следующего, чтобы запросить ввод:

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

typedef struct {    /* typedef for struct containing tank vals */
    int ox,
        nit,
        wt;
} tank_t;

void empty_line (FILE *fp)  /* simple function to strip comments from */
{                           /* your input file */
    int c = fgetc (fp);

    while (c != '\n' && c != EOF)
        c = fgetc (fp);
}

int main (int argc, char **argv) {

    int ndivers = 0,        /* number of divers */
        oxreq = 0,          /* minimum oxygen required */
        nitreq = 0,         /* minimum nitrogen required */
        n = 0,              /* number of cylinders actually read */
        ncyl = 0,           /* number of cylinders from input file */
        wtmin = INT_MAX,    /* minimum weight (initialize to INT_MAX) */
        *indexes = NULL,    /* pointer to track tank indexes */
        *idx = NULL;        /* pointer to temp index */
    tank_t *tanks = NULL, best = { .ox = 0 };   /* pointer to tanks struct */
    /* open file given as 1st argument or read from stdin */
    FILE *fp = argc > 1 ? fopen (argv[1], "r") : stdin;

    if (!fp) {  /* validate file open for reading */
        fprintf (stderr, "error: file open failed '%s'.\n", argv[1]);
        return 1;
    }

    if (fp == stdin)    /* prompt for no. of divers */
        fputs ("enter number of divers: ", stdout);

    /* validate number of divers read */
    if (fscanf (fp, "%d", &ndivers) != 1 || ndivers < 1) {
        fprintf (stderr, "error: read failed - number of divers.\n");
        return 1;
    }
    empty_line (fp);    /* strip remaining comments in line */

    if (fp == stdin)    /* prompt for no. of divers */
        fputs ("enter required oxygen and nitrogen: ", stdout);

    /* validate required ox and nit read from file */
    if (fscanf (fp, "%d %d", &oxreq, &nitreq) != 2 || 
                oxreq < 1 || nitreq < 1) {
        fprintf (stderr, "error: read failed - ox, nit required.\n");
        return 1;
    }
    empty_line (fp);

    if (fp == stdin)    /* prompt for no. of divers */
        fputs ("enter number of cylinders: ", stdout);

    /* validate number of cylinders read from file */
    if (fscanf (fp, "%d", &ncyl) != 1 || ncyl < 1) {
        fprintf (stderr, "error: read failed - no. of cylinders.\n");
        return 1;
    }
    empty_line (fp);

    /* allocate/validate storage for ncyl integers */
    if ((indexes = calloc (ncyl, sizeof *indexes)) == NULL) {
        perror ("calloc-indexes");
        return 1;
    }

    /* allocate/validate storage for ncyl tanks */
    if ((tanks = calloc (ncyl, sizeof *tanks)) == NULL) {
        perror ("calloc-tanks");
        return 1;
    }

    if (fp == stdin)    /* prompt for no. of divers */
        fprintf (stdout, "enter cylinder info (ox, nit, wt.) per-line:\n\n"
                "  enter info for cylinder[%2d]: ", n + 1);

    /* read/validate tank information - store in tanks */
    while (fscanf (fp, "%d %d %d", &tanks[n].ox, 
            &tanks[n].nit, &tanks[n].wt) == 3) {
        empty_line (fp);
        if (++n == ncyl)
            break;
        if (fp == stdin)    /* prompt for no. of divers */
            fprintf (stdout, "  enter info for cylinder[%2d]: ", n + 1);
        }
    if (fp != stdin) fclose (fp);   /* close file if not stdin */

    /* allocate/validate storage for temp indexes (idx) */
    if ((idx = calloc (n, sizeof *idx)) == NULL) {
        perror ("calloc-idx");
        return 1;
    }

    /* loop over each tank to use as beginning in calc */
    for (int i = 0; i < n; i++) {
        int j = i + 1;      /* set 2nd index as next tank */
        memset (idx, 0, sizeof *idx * n);   /* zero working index */
        /* use a temp tank_t struct tmp to accumulate values */
        tank_t tmp = { tanks[i].ox, tanks[i].nit, tanks[i].wt };
        idx[i] = 1;                     /* set 1st index value in tmp index */
        while (j < n) {                 /* loop over remaining tanks */
            idx[j] = 1;                 /* set next index as used */
            tmp.ox += tanks[j].ox;      /* add next tank ox */
            tmp.nit += tanks[j].nit;    /* add next tank nit */
            tmp.wt += tanks[j].wt;      /* add next tank wt */
            /* check if total ox & nit meet min, & wt < current min */
            if (tmp.ox > oxreq && tmp.nit > nitreq && tmp.wt < wtmin) {
                best = tmp;             /* save ox, nit & wt in best */
                wtmin = tmp.wt;         /* update minimum wt */
                memcpy (indexes, idx, n * sizeof *idx); /* copy to indexes */
                memset (idx, 0, sizeof *idx * n);   /* re-zero idx */
                memset (&tmp, 0, sizeof tmp);   /* zero tmp tank */
                idx[i] = 1;                     /* set 1st tank index */
                tmp.ox = tanks[i].ox;   /* set 1st tank values */
                tmp.nit = tanks[i].nit;
                tmp.wt = tanks[i].wt;
            }
            j++;    /* increment 2nd tank counter */
        }
    }
    free (idx); /* free temp index */
    free (tanks);   /* free tanks data - done with it */

    /* output results */
    printf ("\nbest tank combo that meets: O2 >= %d, N >= %d\n\n"
            "  O2: %d\n  N : %d\n  wt: %d\n\n  tanks:",
            oxreq, nitreq, best.ox, best.nit, best.wt);
    for (int i = 0; i < n; i++)
        if (indexes[i])
            printf (" %d", i + 1);
    putchar ('\n');

    free (indexes); /* free final indexes */

    return 0;
}

Пример использования / Вывод (чтение из стандартного ввода с подсказками)

$ ./bin/tankopt2
enter number of divers: 1
enter required oxygen and nitrogen: 5 60
enter number of cylinders: 5
enter cylinder info (ox, nit, wt.) per-line:

  enter info for cylinder[ 1]: 3 36 120
  enter info for cylinder[ 2]: 10 25 129
  enter info for cylinder[ 3]: 5 50 250
  enter info for cylinder[ 4]: 1 45 130
  enter info for cylinder[ 5]: 4 20 119

best tank combo that meets: O2 >= 5, N >= 60

  O2: 13
  N : 61
  wt: 249

  tanks: 1 2