Multiple knapsack total value optimization

Question

Problem description:

A store has N boxes where sequences of bottles can be placed (a sequence can be empty), with each box having a bonus factor c_i and a weight l_i.

• There are only K bottles allowed in the store, each with a weight t_j and a base score p_j. Be careful: the base score can be negative!
• A bottle can be placed at most once in each box of the store, and no bottle can be placed partially: it must start and end within a box.
• If a bottle is placed in two consecutive boxes, its score is reduced to ⌊p_j / 2⌋; for example, if p_j = 5, the new score is 2. A bottle placed in box i, but not placed in box i + 1, will have its full score in box i + 2.
• The final score of a sequence of bottles ⟨m_1, ..., m_r⟩ in a box with bonus factor c_i is given by the sum of the scores of each of the r bottles times c_i. For example, if the scores of the bottles are ⟨1, ⌊7/2⌋, 2, 5⟩ in c_i = 10, then the total value of the sequence of bottles is (1 + 3 + 2 + 5) · 10 · 4 = 440.

Test Cases
Input Format:
Each test case consists of several lines. The first line contains two integers, N and K, representing the number of boxes in the store and the number of bottles cataloged in the store; it is guaranteed that 1 ≤ N ≤ 100 and 1 ≤ K ≤ 10. Each of the N following lines describes a box in the store. The i-th line contains two integers: c_i, which represents the bonus factor of the box (1 ≤ c_i ≤ 100) and l_i, which represents the weight of the box (1 ≤ l_i ≤ 10^6). Following this, there are K lines, each describing a bottle. The j-th line contains two integers: the base score p_j (−10^6 ≤ p_j ≤ 10^6) of the bottle and the weight t_j required to place the bottle (1 ≤ t_j ≤ 10^6); assume that the bottles are numbered from 1 to K in the order given in the input.

Output Format:
The output contains multiple lines. The first line should print a single integer T, representing the maximum total score you can achieve. Following this, there are N lines, each with several integers. The i-th of these lines represents the i-th box in the store. The first integer n_i in that line represents the number of bottles to be placed in the box; then, n_i numbers should be printed, each representing a bottle placed in the i-th box.

I have this source code for now but I am not getting what I need to make to consider the fact that skiping one or more bottles may be the best option 'cause they will regain their value in the next box.

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
using namespace std;
void knapsack_multiple(const vector<int>& profit, const vector<int>& weight, const vector<int>& capacities, const vector<double>& multipliers) {
 int N = profit.size();
 int X = capacities.size();
 vector<int> total_profits(X, 0); // To store total profit for each knapsack
 vector<int> last_included(N, -1); // Tracks the last knapsack where each item was included
 for (int x = 0; x < X; ++x) {
 vector<vector<int>> dp(N + 1, vector<int>(capacities[x] + 1, 0));
 vector<vector<bool>> selected(N + 1, vector<bool>(capacities[x] + 1, false));
 // Fill DP table for the current knapsack
 for (int i = 1; i <= N; ++i) {
 // Start with the original profit
 double current_profit = profit[i - 1];
 
 // Apply the profit reduction if the item was included in the previous knapsack
 if (x - 1 != -1 && last_included[i - 1] == x - 1) {
 current_profit /= 2;
 }
 for (int w = 0; w <= capacities[x]; ++w) {
 if (weight[i - 1] <= w) {
 if (dp[i - 1][w] < dp[i - 1][w - weight[i - 1]] + current_profit) {
 dp[i][w] = dp[i - 1][w - weight[i - 1]] + current_profit;
 selected[i][w] = true;
 } else {
 dp[i][w] = dp[i - 1][w];
 }
 } else {
 dp[i][w] = dp[i - 1][w];
 }
 }
 }
 // Determine which items were selected
 int total_profit = dp[N][capacities[x]];
 int items_count = 0; // Track the number of items in this knapsack
 total_profits[x] = total_profit; // Store the total profit for this knapsack
 cout << "Knapsack " << (x + 1) << " (Capacity: " << capacities[x] << ", Multiplier: " << multipliers[x] << "):\n";
 cout << "Items selected:\n";
 int w = capacities[x];
 for (int i = N; i > 0; --i) {
 if (selected[i][w]) {
 cout << "Item " << i << " (Weight: " << weight[i - 1] << ", Original Profit: " << profit[i - 1] << ", Adjusted Profit: " << (last_included[i - 1] == x - 1 ? profit[i - 1] / 2 : profit[i - 1]) << ")\n";
 
 // Update the last knapsack this item was included in
 last_included[i - 1] = x;
 w -= weight[i - 1];
 items_count++; // Increment the number of items
 }
 }
 // Apply the multiplier and number of items to the total profit
 if (items_count > 0) {
 total_profit *= multipliers[x];
 total_profit *= items_count; // Multiply by the number of items
 }
 cout << "Total profit for knapsack " << (x + 1) << " after applying multiplier and item count: " << total_profit << "\n\n";
 // Store the final profit in the total_profits array
 total_profits[x] = total_profit;
 }
 // Print the total sum of all profits
 int total_sum_profits = accumulate(total_profits.begin(), total_profits.end(), 0);
 cout << "Total sum of all profits: " << total_sum_profits << "\n";
}
int main() {
 vector<int> profit = {50, 1000};
 vector<int> weight = {10, 50};
 vector<int> capacities = {20, 60, 60};
 vector<double> multipliers = {10, 1, 100};
 knapsack_multiple(profit, weight, capacities, multipliers);
 return 0;
}

examples:

input:
3 2
10 20
1 60
100 60
50 10
1000 50

output:
210050
1 1
0
2 1 2

In this example, we have three boxes. The first box has a weight of 20 and a bonus factor of 10, and we can only place the first bottle in it, resulting in a total of 500 points for that box. The second box has a weight of 60, and initially, we could execute both bottles for a score of (1000 + 50/2) · 2 · 1 = 2050. Doing the same in the third box (with a weight of 60 and a factor of 100), we would get an additional (1000/2 + 50/2) · 2 · 100 = 105000, bringing our total to T ′ = 500 +たす 2050 +たす 105000 =わ 107550. However, note that if we do not place any bottles in box 2, we can double our score from box 3, which gives us T = 500 +たす 0 +たす 210000 =わ 210500.

• Thomas Matthews: What are the results when you used a debugger? Which line is at fault? What are the values of the variables? What are the expected values of the variables?
• selbie: "If a bottle is placed in two consecutive boxes" - what does that even mean? I mean, how does a single bottle wind up in two boxes? I usually love trying to solve these kinds of challenges. But this one just sounds exhaustive. And whoever gave it to you didn't proofread their own enthusiastic ideas of a coding challenge.
• selbie: I think the problem is trying to say is that the sum of weights of the bottles in a a box can't exceed the weight of the box. ("weight of box" is really "capacity of box" - thus creating the knapsack problem). I still don't get the "consecutive bottle" thing. I think you are trying to say is two consecutive bottles (not boxes) in the same box incur a score penalty.
• selbie: I'm fairly certain the problem can be resolved with dynamic programming and some adjustments to the standard recursion patterns used in dynamic programming problems. But I can't even attempt it, because your description of the scoring algorithm makes zero sense. If you can explain the scoring algorithm better, I can probably show you an easy solution.
• greybeard: Where you present something you did not come up with yourself, tell who did and where you encountered it.