-1

i used dynamic programming to solve knapsack problem.

#include <iostream>
using namespace std;
#define number 4 // number of item type

typedef struct iteml
{
    int itemw; // [weight of item]
    int itemv; // [value of item]
    char name[30]; // [name of item]
}iteml;

int main()
{
    int item_number = number; // number of item type
    int backpack_weight; //maximum weigth of backpack

    iteml item[number+1]; // [number of item type +1]
    item[1] = { 10, 6, "platinum" };
    item[2] = { 15, 5, "gold" };
    item[3] = { 25, 4, "silver" };
    item[4] = { 50, 1, "steel" };

    int dp[number+1][61] = { 0, }; // [number of item type +1] [maximum weigth of backpack]
    int i, w = 1;

    cout << "type maximum weigth of backpack. : ";
    cin >> backpack_weight;

    for (i = 1; i <= item_number; i++)
    {
        for (w = 1; w <= backpack_weight; w++)
        {
            if (item[i].itemw<= w)
            { 
                if ((item[i].itemv + dp[i - 1][w - item[i].itemw]) > dp[i - 1][w])
                {
                    dp[i][w] = item[i].itemv + dp[i - 1][w - item[i].itemw];
                }
                else
                {
                    dp[i][w] = dp[i - 1][w];
                }
            }
            else
            {
                dp[i][w] = dp[i - 1][w];
            }
        }
    }

    printf("%d", dp[item_number][backpack_weight]);
    return 0;
}

input data

60

output data

15

but i also want to print which items are selected for ex)

15
platinum
gold
silver

first, i added new int called calltime in struct

typedef struct iteml
{
    int itemw; // [weight of item]
    int itemv; // [value of item]
    int calltime; 
    char name[30]; // [name of item]
}iteml;

and i thought if i add some item[n].calltime-- or item[n].calltime++ i was able to know which items were selected, but it was totally impossible

RyuJin
  • 1
  • 1
  • "`#define number 4`" - ewww, why a *macro*? Why not just a proper `const` or `constexpr` variable? And C-style arrays? Why not `std::array` or `std::vector`? – Jesper Juhl Nov 25 '22 at 20:34
  • [Why is "using namespace std;" considered bad practice?](https://stackoverflow.com/questions/1452721/why-is-using-namespace-std-considered-bad-practice) – Jesper Juhl Nov 25 '22 at 20:37
  • "`typedef struct iteml`" - are you writing C or C++? The `printf("%d" ...` later seems to also be a vote for C.. – Jesper Juhl Nov 25 '22 at 20:38

1 Answers1

0

i solved by adding this code

int num = item_number;
    int weight = backpack_weight;
    while (num > 0) {
        if (dp[num][weight] != dp[num - 1][weight]) {
            printf("%s ", item[num].name);
            weight -= item[num - 1].itemw;
        }
        num -= 1;
    }
RyuJin
  • 1
  • 1