I think i got the logic

#1

but i can not figure out how to write the code , can you please provide a clean code of this !!

#2

@aryan_007,
What is the recurrence relation you came up with…?

#3

image
image1920×1080 189 KB

#4

but i can’t figure out that how will i distribute in the sets and then iterate on them and again when the knapasck is filled with at least one item of each set then again i need to iterate on all elements to get the remaining knapasack filled

#5

@aryan_007,
You can ensure at least one by something like dp[i-1][j-wi] !=0.
Also, don’t mind complexity much at first, just code the correct recurrence even if it’s n^3, we will optimise afterwards.

#6

okay i am able to take out at least one element from each set and grab the maxmium weight but now how to remove those elements to work on the remaining array like 0/1 knapsack.

#7

image
image619×851 164 KB

#8

@aryan_007,
You shouldn’t relax when dp[i-1][j-k] = 0, as then it means you are taking 0 element till i-1, which we cannot do as we have to take at least one of each color.

#9

no sir , i didn’t relaxed there it is the reason i took vis map so that i know if it is taken only then i will have its contribution later and sir taking at least one element is working fine , the problem is how to take remaining elements . I mean i have taken at least 1 element from each set now next how to proceed.

#10

@aryan_007,
I just wanted to ask why is there all 0’s in m=2 row of dp, doesn’t this means you haven’t picked up a single item of m=2 color?
Anyways, here is a implementation of this idea: Link.

#11

no no that m=2 is actually m=0 , above 2 lines are the input not the dp table , dp table start from 000000000 line

#12

it is kind of hard to follow through the code , can you please write some comments from here to here .

vector<vector> col(m);

for (int i = 1; i <= n; i++) {

    col[c[i] - 1].push_back(w[i]);

}

vector<bool> dp(x + 2, false);

for (int j = 0; j <= (int)col[0].size() - 1; j++) dp[col[0][j]] = true;

for (int i = 1; i <= m - 1; i++) {

    vector<bool> new_dp(x + 2, false);

    for (int j = 0; j <= x; j++) {

        if (dp[j]) {

            for (int k = 0; k <= (int)col[i].size() - 1; k++) new_dp[min(x + 1, j + col[i][k])] = true;

        }

    }

    dp = new_dp;

}
#13

@aryan_007,
Both our codes are pretty much the same, col[c[i]] is same as your mp, basically accumulating all weights of same colour. Also even our dp is same. You can see in your dp, transition only depends on dp[i-1] and not any previous like dp[i-2], dp[i-3] etc. So it is just a space optimisation technique. We only keep last dp row, rather than the whole 2D table, and from that last row we calculate the new row, new_dp is basically the new calculated row of dp, which will replace the old one as we leave each loop.

And also in my code

if (dp[j]) { // if(dp[j] != 0)

ensures that I only take my answer from a column which is non-zero, which ensures that I take at least 1 for each color.

And my inner loop is same as yours

for (int j = 0; j <= x; j++) {

Just you have used range based and I have used a simple for loop.

1 Like
#14

okayyy sir , thankyou sir !!