Каждый раз, когда я меняю константу, результат отличается - PullRequest
Новая
       17

Каждый раз, когда я меняю константу, результат отличается

0 голосов
/ 28 мая 2019

Я хочу закодировать проблему 01 рюкзак в C ++. Каждый раз, когда я изменяю значение константы MAX на другое значение, такое как 100,90 или 80, результат отличается. В чем причина? Я использую Visual Studio 2019.

Вводим текстовый файл, например.

20

40 35 18 4 10 2 70 20 39 37 7 5 10 8 15 21 50 40 10 30

100 50 45 20 10 5 31 10 20 19 4 3 6 8 12 7 10 2 5 5

137

В первом ряду указано количество предметов, во втором ряду указана цена, в третьем ряду указан вес, а в последнем ряду указан размер рюкзака. 

#include <stdio.h>
#include <time.h>
#define MAX 100
#define CLOCKS_PER_MS CLOCKS_PER_SEC/1000

int X_d[MAX] = { 0 }; //solution vector

int max(int a, int b) {
if (a >= b)
    return a;
else
    return b;
}

void dynamic(int n, int M, int p[], int w[]) {
int result;
int i, y, k;
int P[MAX][MAX] = { 0 };
clock_t start, finish;

start = clock();
for (i = 0; i <= n; i++) {
    for (y = 0; y <= M; y++) {
        if (i == 0 || y == 0)
            P[i][y] = 0;
        else if (w[i - 1] > y)
            P[i][y] = P[i - 1][y];
        else
            P[i][y] = max(P[i - 1][y], p[i - 1] + P[i - 1][y - w[i - 1]]);
    }
}
finish = clock();
result = P[n][M];
y = M;
for (i = n; i > 0 && result > 0; i--) {
    if (result == P[i - 1][y]) {
        continue;
    }
    else {
        X_d[i - 1] = 1;
        result = result - p[i - 1];
        y = y - w[i - 1];
    }
}

printf("\n(1) Dynamic Programming");
printf("\nThe maximum profit is $%d", P[n][M]);
printf("\nThe solution vetor X = ( ");
for (k = 0; k < n; k++)
    printf("%d ", X_d[k]);
printf(")\n");
printf("The execution time is %f milliseconds.\n", (float)(finish - start) / CLOCKS_PER_MS);
}

int main() {
int i, j;
int num, M;
int p[MAX] = { 0 }, w[MAX] = { 0 };
FILE* fp = NULL;


fopen_s(&fp, "p2data6.txt", "r");
fscanf_s(fp, "%d", &num);

for (i = 0; i < num; i++)
    fscanf_s(fp, "%d", &p[i]);

for (i = 0; i < num; i++)
    fscanf_s(fp, "%d", &w[i]);

fscanf_s(fp, "%d", &M);

printf("n = %d\n", num);
printf("pi = ");
for (i = 0; i < num; i++)
    printf("%3d ", p[i]);
printf("\nwi = ");
for (i = 0; i < num; i++)
    printf("%3d ", w[i]);
printf("\npi/wi = ");
for (i = 0; i < num; i++)
    printf("%f ", (double)p[i] / w[i]);
printf("\nM = %d\n", M);

dynamic(num, M, p, w);

return 0;
}

1 Ответ

0 голосов
/ 28 мая 2019

Geeks for Geeks имеет очень хорошее объяснение этой проблемы здесь :

Процитирую статью о вундеркиндах для гиков от Sam007:

Простое решение - рассмотреть все подмножества предметов и рассчитать общий вес и стоимость всех подмножеств. Рассмотрим только те подмножества, общий вес которых меньше W. Из всех таких подмножеств выберите подмножество максимальных значений.

1) Оптимальная подструктура: Чтобы рассмотреть все подмножества элементов, может быть два случая для каждого элемента: (1) элемент включен в оптимальный набор, (2) не включен в оптимальный набор. Следовательно, максимальное значение, которое можно получить из n элементов, является максимальным из следующих двух значений. 1) Максимальное значение, полученное n-1 предметами и весом W (исключая n-й предмет). 2) Стоимость n-го предмета плюс максимальное значение, полученное из n-1 предметов, и W минус вес n-го предмета (включая n-й предмет).

Если вес n-го предмета больше W, тогда n-й предмет не может быть включен, и случай 1> является единственной возможностью.

2) Перекрывающиеся подзадачи Ниже приводится рекурсивная реализация, которая просто следует рекурсивной структуре, упомянутой выше.

...