He took as a basis the algorithm for solving the backpack problem from the Sedgwik book, but the program does not work correctly. For some reason, it always returns zero. In his book, the code is commented very badly: the assignments of variables are spoken somewhere far in the beginning, and there they are not even talking about variables, but about entering such and such numbers marked M. The code is very unpleasant, and it is difficult to make it beautiful procedure. Help at least figure out why zero is always displayed.

#include <iostream> #include <cstring> #include <ctime> typedef struct{ int size; int val; } Item; const int n = 10; // Число предметов const int m = 50; // Емкость рюкзака const int size = 50; Item items[n]; int max_known[size]; Item item_known[size]; int knap(int cap){ int space; int max; int maxi; int t; for(int i = 0; i < size; i++) std::cout << max_known[i] << " "; std::cout << std::endl; if(max_known[cap] != -1) return max_known[cap]; for(int i = 0, max = 0; i < n; i++) if((space = cap - items[i].size) >= 0) if((t = knap(space) + items[i].val) > max){ max = t; maxi = i; } max_known[cap] = max; item_known[cap] = items[maxi]; return max; } int main(){ std::memset(max_known, -1, size * sizeof(int)); // Создаем рандомные вещи std::srand(time(NULL)); for(int i = 0; i < n; i++){ Item it; it.size = 1 + std::rand() % 15; it.val = 1 + std::rand() % 701; items[i] = it; } std::cout << knap(m) << std::endl; int pause; std::cin >> pause; }
  • one
    Take a debugger and see how the program works. - Vladimir Martyanov

2 answers 2

You are called from the element of the max_known[50] array max_known[50] , which, generally speaking, is not, and there is clearly not -1.

To get rid of the arrays and memset use std::vector<int> . Well, it's still cool not to initialize something in conditions :)

    The first thing that catches your eye is that you create an uninitialized variable max in the function body, and you create another variable max in the loop initialization statement, which you initialize to zero.

    As a result, the second variable changes in the body of the loop, the one that was created at the beginning of the loop (and will be deleted at the end of the loop), and the first, uninitialized one is returned.

    PS I did not check the algorithm itself.

    PPS Compile with -Wall , this is always useful.

    PPPS And also, pray tell, why do you need global variables?

    • Regarding the creation of a variable in the header of the loop: I now made it so that the variables are created at the beginning of the function, and only initialized in the loop. It's all right? But the program still does not work correctly. And what to do with global variables, for example, with arrays? Some programs are written with beautiful program logic, and all these algorithms must either be implemented with the help of several classes, or written like this in the style of the 70s. ideone.com/1h1H4A - typemoon
    • This is how it works. Can you advise how to improve the architecture of the program? ideone.com/mQbUJn - typemoon pm
    • Very simple. You need to understand the algorithm and write it yourself =) And if in the case, get rid of global variables and constants - it is always good. - Zelta
    • I figured out and know how to fill the two-dimensional table for this algorithm. It is possible to get rid of constants, but how to get rid of arrays, if their size actually should change depending on the input data? - typemoon
    • Pass them to the function. Or create directly in the function ( new / delete ). - Zelta