Knapsack problem - Find which items are taken
.everyoneloves__top-leaderboard:empty,.everyoneloves__mid-leaderboard:empty,.everyoneloves__bot-mid-leaderboard:empty{ height:90px;width:728px;box-sizing:border-box;
}
I need to find every optimal solution for knapsack problem.
Here is my code
void knapSack(int W, int wt, int val, int n)
{
int i, w;
int K[W+1][n+1];
for (w = 0; w <= W; w++)
{
for(i=0;i<=n;i++){
if(i==0)
K[w][i]=0;
if(w<wt[i-1] && i!=0)
K[w][i]=K[w][i-1];
if(w>=wt[i-1] && i!=0)
K[w][i]=max(K[w][i-1],K[w-wt[i-1]][i-1]+val[i-1]);
}
}
i=n;
int j=W;
while(i,j>0){
if(K[j][i]!=K[j][i-1]){
cout<<"Item "<<i<<" is in the bag"<<endl;
i=i-1;
j=j-wt[i-1];
}
else
i=i-1;
}
}
Input data is:
4 6 //n W
2 1 //p1 w1
3 2 //p2 w2
3 4 //p3 w3
4 5 //p4 w4
And output should be like this:
1 4
2 3
The first part of my code which is packing the bag is working great, but the secound part where I try to find which items were taken is giving me answer: item 3, item 2, item 1 which is wrong because there is 2 solutions: you take item 1 and 4 or item 2 or 3. How can I fix this?
In the picture below there is table with table solution of packing
c++ algorithm knapsack-problem
edited Nov 16 '18 at 16:19
nightfury1204
1,779510
asked Nov 16 '18 at 14:17
szybkikonszybkikon
63
add a comment |
I need to find every optimal solution for knapsack problem.
Here is my code
void knapSack(int W, int wt, int val, int n)
{
int i, w;
int K[W+1][n+1];
for (w = 0; w <= W; w++)
{
for(i=0;i<=n;i++){
if(i==0)
K[w][i]=0;
if(w<wt[i-1] && i!=0)
K[w][i]=K[w][i-1];
if(w>=wt[i-1] && i!=0)
K[w][i]=max(K[w][i-1],K[w-wt[i-1]][i-1]+val[i-1]);
}
}
i=n;
int j=W;
while(i,j>0){
if(K[j][i]!=K[j][i-1]){
cout<<"Item "<<i<<" is in the bag"<<endl;
i=i-1;
j=j-wt[i-1];
}
else
i=i-1;
}
}
Input data is:
4 6 //n W
2 1 //p1 w1
3 2 //p2 w2
3 4 //p3 w3
4 5 //p4 w4
And output should be like this:
1 4
2 3
The first part of my code which is packing the bag is working great, but the secound part where I try to find which items were taken is giving me answer: item 3, item 2, item 1 which is wrong because there is 2 solutions: you take item 1 and 4 or item 2 or 3. How can I fix this?
In the picture below there is table with table solution of packing
c++ algorithm knapsack-problem
edited Nov 16 '18 at 16:19
nightfury1204
1,779510
asked Nov 16 '18 at 14:17
szybkikonszybkikon
63
Not your problem, buti,j>0isn't doing what you think it's doing - in this case it's essentially the same asj>0. You probably wantedi>0 && j>0.
– Dukeling
Nov 16 '18 at 14:58
Movei=i-1one line down. With some debugging, you probably could've figured out that section of the code thinks the third item weighs 2, the second item 1 and the first item 0 (instead of 4,2,1), which would've indicated that you're looking at the wrong weight values.
– Dukeling
Nov 16 '18 at 15:41
add a comment |
I need to find every optimal solution for knapsack problem.
Here is my code
void knapSack(int W, int wt, int val, int n)
{
int i, w;
int K[W+1][n+1];
for (w = 0; w <= W; w++)
{
for(i=0;i<=n;i++){
if(i==0)
K[w][i]=0;
if(w<wt[i-1] && i!=0)
K[w][i]=K[w][i-1];
if(w>=wt[i-1] && i!=0)
K[w][i]=max(K[w][i-1],K[w-wt[i-1]][i-1]+val[i-1]);
}
}
i=n;
int j=W;
while(i,j>0){
if(K[j][i]!=K[j][i-1]){
cout<<"Item "<<i<<" is in the bag"<<endl;
i=i-1;
j=j-wt[i-1];
}
else
i=i-1;
}
}
Input data is:
4 6 //n W
2 1 //p1 w1
3 2 //p2 w2
3 4 //p3 w3
4 5 //p4 w4
And output should be like this:
1 4
2 3
The first part of my code which is packing the bag is working great, but the secound part where I try to find which items were taken is giving me answer: item 3, item 2, item 1 which is wrong because there is 2 solutions: you take item 1 and 4 or item 2 or 3. How can I fix this?
In the picture below there is table with table solution of packing
c++ algorithm knapsack-problem
edited Nov 16 '18 at 16:19
nightfury1204
1,779510
asked Nov 16 '18 at 14:17
szybkikonszybkikon
63
I need to find every optimal solution for knapsack problem.
Here is my code
void knapSack(int W, int wt, int val, int n)
{
int i, w;
int K[W+1][n+1];
for (w = 0; w <= W; w++)
{
for(i=0;i<=n;i++){
if(i==0)
K[w][i]=0;
if(w<wt[i-1] && i!=0)
K[w][i]=K[w][i-1];
if(w>=wt[i-1] && i!=0)
K[w][i]=max(K[w][i-1],K[w-wt[i-1]][i-1]+val[i-1]);
}
}
i=n;
int j=W;
while(i,j>0){
if(K[j][i]!=K[j][i-1]){
cout<<"Item "<<i<<" is in the bag"<<endl;
i=i-1;
j=j-wt[i-1];
}
else
i=i-1;
}
}
Input data is:
4 6 //n W
2 1 //p1 w1
3 2 //p2 w2
3 4 //p3 w3
4 5 //p4 w4
And output should be like this:
1 4
2 3
The first part of my code which is packing the bag is working great, but the secound part where I try to find which items were taken is giving me answer: item 3, item 2, item 1 which is wrong because there is 2 solutions: you take item 1 and 4 or item 2 or 3. How can I fix this?
In the picture below there is table with table solution of packing
c++ algorithm knapsack-problem
c++ algorithm knapsack-problem
edited Nov 16 '18 at 16:19
nightfury1204
1,779510
asked Nov 16 '18 at 14:17
szybkikonszybkikon
63
edited Nov 16 '18 at 16:19
nightfury1204
1,779510
asked Nov 16 '18 at 14:17
szybkikonszybkikon
63
edited Nov 16 '18 at 16:19
nightfury1204
1,779510
edited Nov 16 '18 at 16:19
nightfury1204
1,779510
edited Nov 16 '18 at 16:19
nightfury1204
1,779510
1,779510
asked Nov 16 '18 at 14:17
szybkikonszybkikon
63
asked Nov 16 '18 at 14:17
szybkikonszybkikon
63
asked Nov 16 '18 at 14:17
szybkikonszybkikon
63
63
Not your problem, buti,j>0isn't doing what you think it's doing - in this case it's essentially the same asj>0. You probably wantedi>0 && j>0.
– Dukeling
Nov 16 '18 at 14:58
Movei=i-1one line down. With some debugging, you probably could've figured out that section of the code thinks the third item weighs 2, the second item 1 and the first item 0 (instead of 4,2,1), which would've indicated that you're looking at the wrong weight values.
– Dukeling
Nov 16 '18 at 15:41
add a comment |
Not your problem, buti,j>0isn't doing what you think it's doing - in this case it's essentially the same asj>0. You probably wantedi>0 && j>0.
– Dukeling
Nov 16 '18 at 14:58
Movei=i-1one line down. With some debugging, you probably could've figured out that section of the code thinks the third item weighs 2, the second item 1 and the first item 0 (instead of 4,2,1), which would've indicated that you're looking at the wrong weight values.
– Dukeling
Nov 16 '18 at 15:41
Not your problem, but
i,j>0 isn't doing what you think it's doing - in this case it's essentially the same as j>0. You probably wanted i>0 && j>0.– Dukeling
Nov 16 '18 at 14:58
Not your problem, but
i,j>0 isn't doing what you think it's doing - in this case it's essentially the same as j>0. You probably wanted i>0 && j>0.– Dukeling
Nov 16 '18 at 14:58
Move
i=i-1 one line down. With some debugging, you probably could've figured out that section of the code thinks the third item weighs 2, the second item 1 and the first item 0 (instead of 4,2,1), which would've indicated that you're looking at the wrong weight values.– Dukeling
Nov 16 '18 at 15:41
Move
i=i-1 one line down. With some debugging, you probably could've figured out that section of the code thinks the third item weighs 2, the second item 1 and the first item 0 (instead of 4,2,1), which would've indicated that you're looking at the wrong weight values.– Dukeling
Nov 16 '18 at 15:41
add a comment |
1 Answer
1
active
oldest
votes
I would use the same formula that you use to maximize the value to see which items picked i.e.
if (K[w][i] == K[w-wt[i-1]][i-1] + val[i-1])
then item i is picked else this is not picked and go to previous item i-1.
Also there could be more than 1 set of items which when picked can yield the maximum value.
In that case look for each such value in the array K[W][..] for the maximum value K[W][n] and traverse the array from that point to get the picked items.
Code is :
void knapSack(int W, int wt, int val, int n)
{
int i, w;
int K[W+1][n+1];
for (w = 0; w <= W; w++)
{
for(i=0;i<=n;i++){
if(i==0)
K[w][i]=0;
if(w<wt[i-1] && i!=0)
K[w][i]=K[w][i-1];
if(w>=wt[i-1] && i!=0)
K[w][i]=max(K[w][i-1],K[w-wt[i-1]][i-1]+val[i-1]);
}
}
cout << "n" << "Maximum value obtained is : " << K[W][n] << "n";
int j;
for ( j=1; j<=n; j++ ) {
if (K[W][j] == K[W][n]) {
int w = W;
int i = j;
while(i>0 && w>0){
if (K[w][i] == K[w-wt[i-1]][i-1] + val[i-1]) {
cout << "Item " << i << " is in the bag" << "n";
w = w - wt[i-1];
i--;
} else {
i--;
}
}
cout<< "n";
}
}
}
answered Nov 16 '18 at 15:59
SomeDudeSomeDude
4,43531428
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
StackExchange.using("externalEditor", function () {
StackExchange.using("snippets", function () {
StackExchange.snippets.init();
});
});
}, "code-snippets");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "1"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f53339606%2fknapsack-problem-find-which-items-are-taken%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
I would use the same formula that you use to maximize the value to see which items picked i.e.
if (K[w][i] == K[w-wt[i-1]][i-1] + val[i-1])
then item i is picked else this is not picked and go to previous item i-1.
Also there could be more than 1 set of items which when picked can yield the maximum value.
In that case look for each such value in the array K[W][..] for the maximum value K[W][n] and traverse the array from that point to get the picked items.
Code is :
void knapSack(int W, int wt, int val, int n)
{
int i, w;
int K[W+1][n+1];
for (w = 0; w <= W; w++)
{
for(i=0;i<=n;i++){
if(i==0)
K[w][i]=0;
if(w<wt[i-1] && i!=0)
K[w][i]=K[w][i-1];
if(w>=wt[i-1] && i!=0)
K[w][i]=max(K[w][i-1],K[w-wt[i-1]][i-1]+val[i-1]);
}
}
cout << "n" << "Maximum value obtained is : " << K[W][n] << "n";
int j;
for ( j=1; j<=n; j++ ) {
if (K[W][j] == K[W][n]) {
int w = W;
int i = j;
while(i>0 && w>0){
if (K[w][i] == K[w-wt[i-1]][i-1] + val[i-1]) {
cout << "Item " << i << " is in the bag" << "n";
w = w - wt[i-1];
i--;
} else {
i--;
}
}
cout<< "n";
}
}
}
answered Nov 16 '18 at 15:59
SomeDudeSomeDude
4,43531428
add a comment |
I would use the same formula that you use to maximize the value to see which items picked i.e.
if (K[w][i] == K[w-wt[i-1]][i-1] + val[i-1])
then item i is picked else this is not picked and go to previous item i-1.
Also there could be more than 1 set of items which when picked can yield the maximum value.
In that case look for each such value in the array K[W][..] for the maximum value K[W][n] and traverse the array from that point to get the picked items.
Code is :
void knapSack(int W, int wt, int val, int n)
{
int i, w;
int K[W+1][n+1];
for (w = 0; w <= W; w++)
{
for(i=0;i<=n;i++){
if(i==0)
K[w][i]=0;
if(w<wt[i-1] && i!=0)
K[w][i]=K[w][i-1];
if(w>=wt[i-1] && i!=0)
K[w][i]=max(K[w][i-1],K[w-wt[i-1]][i-1]+val[i-1]);
}
}
cout << "n" << "Maximum value obtained is : " << K[W][n] << "n";
int j;
for ( j=1; j<=n; j++ ) {
if (K[W][j] == K[W][n]) {
int w = W;
int i = j;
while(i>0 && w>0){
if (K[w][i] == K[w-wt[i-1]][i-1] + val[i-1]) {
cout << "Item " << i << " is in the bag" << "n";
w = w - wt[i-1];
i--;
} else {
i--;
}
}
cout<< "n";
}
}
}
answered Nov 16 '18 at 15:59
SomeDudeSomeDude
4,43531428
add a comment |
I would use the same formula that you use to maximize the value to see which items picked i.e.
if (K[w][i] == K[w-wt[i-1]][i-1] + val[i-1])
then item i is picked else this is not picked and go to previous item i-1.
Also there could be more than 1 set of items which when picked can yield the maximum value.
In that case look for each such value in the array K[W][..] for the maximum value K[W][n] and traverse the array from that point to get the picked items.
Code is :
void knapSack(int W, int wt, int val, int n)
{
int i, w;
int K[W+1][n+1];
for (w = 0; w <= W; w++)
{
for(i=0;i<=n;i++){
if(i==0)
K[w][i]=0;
if(w<wt[i-1] && i!=0)
K[w][i]=K[w][i-1];
if(w>=wt[i-1] && i!=0)
K[w][i]=max(K[w][i-1],K[w-wt[i-1]][i-1]+val[i-1]);
}
}
cout << "n" << "Maximum value obtained is : " << K[W][n] << "n";
int j;
for ( j=1; j<=n; j++ ) {
if (K[W][j] == K[W][n]) {
int w = W;
int i = j;
while(i>0 && w>0){
if (K[w][i] == K[w-wt[i-1]][i-1] + val[i-1]) {
cout << "Item " << i << " is in the bag" << "n";
w = w - wt[i-1];
i--;
} else {
i--;
}
}
cout<< "n";
}
}
}
answered Nov 16 '18 at 15:59
SomeDudeSomeDude
4,43531428
I would use the same formula that you use to maximize the value to see which items picked i.e.
if (K[w][i] == K[w-wt[i-1]][i-1] + val[i-1])
then item i is picked else this is not picked and go to previous item i-1.
Also there could be more than 1 set of items which when picked can yield the maximum value.
In that case look for each such value in the array K[W][..] for the maximum value K[W][n] and traverse the array from that point to get the picked items.
Code is :
void knapSack(int W, int wt, int val, int n)
{
int i, w;
int K[W+1][n+1];
for (w = 0; w <= W; w++)
{
for(i=0;i<=n;i++){
if(i==0)
K[w][i]=0;
if(w<wt[i-1] && i!=0)
K[w][i]=K[w][i-1];
if(w>=wt[i-1] && i!=0)
K[w][i]=max(K[w][i-1],K[w-wt[i-1]][i-1]+val[i-1]);
}
}
cout << "n" << "Maximum value obtained is : " << K[W][n] << "n";
int j;
for ( j=1; j<=n; j++ ) {
if (K[W][j] == K[W][n]) {
int w = W;
int i = j;
while(i>0 && w>0){
if (K[w][i] == K[w-wt[i-1]][i-1] + val[i-1]) {
cout << "Item " << i << " is in the bag" << "n";
w = w - wt[i-1];
i--;
} else {
i--;
}
}
cout<< "n";
}
}
}
answered Nov 16 '18 at 15:59
SomeDudeSomeDude
4,43531428
answered Nov 16 '18 at 15:59
SomeDudeSomeDude
4,43531428
answered Nov 16 '18 at 15:59
SomeDudeSomeDude
4,43531428
answered Nov 16 '18 at 15:59
SomeDudeSomeDude
4,43531428
4,43531428
add a comment |
add a comment |
Thanks for contributing an answer to Stack Overflow!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f53339606%2fknapsack-problem-find-which-items-are-taken%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Not your problem, but
i,j>0isn't doing what you think it's doing - in this case it's essentially the same asj>0. You probably wantedi>0 && j>0.– Dukeling
Nov 16 '18 at 14:58
Move
i=i-1one line down. With some debugging, you probably could've figured out that section of the code thinks the third item weighs 2, the second item 1 and the first item 0 (instead of 4,2,1), which would've indicated that you're looking at the wrong weight values.– Dukeling
Nov 16 '18 at 15:41