How to get the number of items used in an unbounded knapsack problem?

user_15248227 0
Viewed 523

I'm trying to solve an unbounded knapsack problem but I am stuck. I've already solved the main part of the problem which is getting the max value, but I'm also supposed to figure out how many of each item I used in order to get my maximum answer.
The bounds are less than 100 items and less than 100 capacity of the knapsack. The example input is
3 (number of items)
8 (knapsack capacity)
5 21 (weight and value respectively)
3 1
4 15

and the output would be
30 (the maximum value the bag can hold, which is 2 of the 4 weight item)
0 0 2 (how many of each items is in the knapsack)

I have no idea how to print that last line of output, and I've been stuck on this problem for a week. I asked elsewhere, and they said to store the previous state I came from, but I'm not sure how to do that. Here is my code so far. Any help is appreciated.

#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <cstring>
#include <string>

using namespace std;

int wt[101];
int val[101];
int ans[101];
int cnt[101];

int knapsack(int s, int N, int val[], int wt[]){
    
    for(int i=0;i<=s;i++){
        for(int j=0;j<N;j++){
            if(wt[j]<=i){
                int tmp = ans[i];
                ans[i] = max(ans[i], ans[i-wt[j]] + val[j]);
                
            }
        }
    }
    return ans[s];
}
int main() {
    
    int N, s, i, j, k, w, p;
    
    
    scanf("%d", &N);
    scanf("%d", &s);
    for(i=0;i<N;i++){
        scanf("%d %d", &wt[i], &val[i]);
    }
    
    printf("%d\n", knapsack(s, N, val, wt));
    
    
    
    
    return 0;
}
knapsack-problem c++
1 Answers

I think you need to think about your basic organization. I'm not going to do your homework for you, but I'll try to give some hints.

Your explanation of the knapsack problem seems flawed. Let me make sure we have the same problem.

You have a knapsack (a backpack). It can hold up to N "pounds".

You have several piles of things you can put into the knapsack. Each have a weight and a value.

The idea is to figure out how to stuff the knapsack with the highest amount of value.

It's interesting if you think of it differently. Imagine you won a shopping spree in a store. You get to fill the shopping cart, and you want to make away with the greatest value possible. So you head to the most expensive items and fill the cart as full as you can, but when you're almost done, you then head to the small items and stuff the corners.

In the end, you need to know:

-What's the total dollar value of the things in the cart -And what's actually in it

This is actually kind of a tricky problem. I'd start with this: the structure of my data. I'd use a class to hold the possible items:

class Item {
public:
     int weight;
     int value;
};

It doesn't sound like you have to worry about container classes (std::vector), so let's make an array:

Item items[100];

The code you have for reading the input is mostly good, but instead of reading into your individual arrays, you would do something like this:

for(index = 0; i < N; index++){
    Item & item = items[index];
    scanf("%d %d", &item.weight, &item.value);
}

Now the data for your items is stored together, which helps in thinking about your items.

I'm going to talk about some stylistic things for a moment. First, I don't like your variable names. It's good to avoid abbreviations. You'll see I spell them out. Also, variable names of a single letter are hard to search for. You'll see I used index instead of i. You'll have a million instances of i in your code, but not so many instances of index.

Another stylistic thing to make the code easier to read: whitespace. We can afford it. I don't like to see stuff shoved all together, because I think that makes it a lot harder to read. Don't be afraid of spaces.

Clearly, those two paragraphs are an opinion, so take it for what it's worth.

At this point, you have to solve the problem. How do you fill the knapsack / cart / backpack the most optimally.

Have you learned about recursion yet? Think of this code.

Imagine a method called findSolution. You're going to call it recursively, although you can do this in a double-nested loop, too.

The method decides "we're best if we don't use any of the first item. What's the best solution using the remaining items?" It calls itself, but says to skip the first item.

Then it says, "What if I put ONE of the first item in?" And then calls itself on the remaining list.

When that gets back, is sees, "Oh, putting 1 in gives me a better total value than if I don't use any, so that's my tentative best solution."

You loop checking until you've use all 8 slots with just the first item, figuring out what is best.

It's tricky to code, might take a little time, but it's one way to solve this. Store the results in another class, then printing it is easy.

user_13619010
Related