0-1 knapsack solve

main.cpp

// https://www.youtube.com/watch?v=nLmhmB6NzcM

std::vector<int> profits = { 1,2,5,6 }; // 5, 8
std::vector<int> weights = { 2,3,4,5 }; //, 4, 9
int m = 8;//20;
int n = weights.size();

std::vector<std::vector<int>> results(n + 1, std::vector<int>(m + 1, 0));

for (int i = 1;i <= n;i++) {
    for (int j = 1;j <= m;j++) {
        if (j >= weights[i - 1])
            results[i][j] = std::max<int>(results[i - 1][j], results[i - 1][j - weights[i - 1]] + profits[i - 1]);
        else
            results[i][j] = results[i - 1][j];
    }
}
printf("\n");
for (int i = 0;i <= n;i++) {
    printf("#%d  ", i);
    for (int j = 0;j <= m;j++)
        printf("%2d ", results[i][j]);
    printf("\n");
}

std::vector<int> takes(n, 0);

int profit = results[n][m];
int j = m;
for (int i = n;i > 0;i--) {
    if (results[i][j] != results[i - 1][j]) {
        takes[i-1] = 1;
        profit -= profits[i-1];
        for (int k = m;k >= 0;k--)
            if (results[i][k] == profit)
                j = k;
    }
}

int total_weight = 0;
for (int i = 0;i < n;i++) {
    total_weight += (takes[i] * weights[i]);
    printf("object#%d %d, %d kg, %d $\n", i + 1, takes[i], weights[i], profits[i]);
}

printf("\n");
printf("total weight: %d\n", total_weight);
printf("max profit: %d\n", results[n][m]);

std::vector<int> line_results(m + 1, 0);
for (int i = 1;i <= n;i++) {
    for (int j=m;j>=weights[i - 1];j--)
        line_results[j] = std::max<int>(line_results[j], line_results[j - weights[i - 1]] + profits[i - 1]);
}
printf("\n\n");
printf("line results optimization:\n");
for (int i = 0;i <= m;i++) {
    printf("%d  ", line_results[i]);
}
printf("\nmax profit: %d\n", line_results[m]);

// must full knapsack
std::vector<std::vector<int>> must_full_results(n + 1, std::vector<int>(m + 1, -1));
must_full_results[0][0] = 0;

for (int i = 1;i <= n;i++) {
    for (int j = 1;j <= m;j++) {
        if (j >= weights[i - 1]) {
            int take;
            if (must_full_results[i - 1][j - weights[i - 1]] == -1)
                take = -1;
            else
                take = must_full_results[i - 1][j - weights[i - 1]] + profits[i - 1];
            must_full_results[i][j] = std::max<int>(must_full_results[i - 1][j], take);
        }
        else
            must_full_results[i][j] = must_full_results[i - 1][j];
    }
}
printf("\nmust full\n");
for (int i = 0;i <= n;i++) {
    printf("#%d  ", i);
    for (int j = 0;j <= m;j++)
        printf("%2d ", must_full_results[i][j]);
    printf("\n");
}

// full line optimization knapsack
std::vector<int> full_knapsack_line_results(m + 1, 0);
for (int i = 1;i <= n;i++) {
    for (int j = weights[i - 1];j<=m;j++)
        full_knapsack_line_results[j] = std::max<int>(full_knapsack_line_results[j], full_knapsack_line_results[j - weights[i - 1]] + profits[i - 1]);
}
printf("\n\n");
printf("full knapsack line results optimization:\n");
for (int i = 0;i <= m;i++) {
    printf("%d  ", full_knapsack_line_results[i]);
}
printf("\nmax profit: %d\n", full_knapsack_line_results[m]);