Multiple 0-1 knapsack
I have a problem were the time in minutes of N songs are given and I have to write the maximum number of time in K CDs.
Input description
The first input line consists of two positive integers N e K ($N le 100$, $K le 3$), which represent respectively the number of songs and te number of cds. The second input line consists of N positive integers, which represent the duration in minutes of each song. The last input line consists of K positive integers, which represent the maximum number of minutes of music that it is possible to record to each cd. No song has more than 50 minutes, and no cd has available more than 50 minutes of space.
Output description
Print a line containing singly the maximum total number of minutes of music that it is possible to record to the cartridges.
To solve this problem I've programmed a dynamic programming solution where the choices are put the $i$th song on each CD or none.
#include <iostream>
#include <algorithm>
#include <string.h>
int dpt[51][51][51][101]; //table for dp
int dp(int *song, int *cd, int n, int k, int element){
if(element == n)
return dpt[ cd[0] ][ cd[1] ][ cd[2] ][element] = 0;
if(dpt[ cd[0] ][ cd[1] ][ cd[2] ][element] != -1)
return dpt[ cd[0] ][ cd[1] ][ cd[2] ][element];
int best = 0;
for (int i = 0; i < k; ++i) {
if(cd[i] >= song[element]){
cd[i] -= song[element];
best = std::max(best,song[element] + dp(song,cd,n,k,element + 1));
cd[i] += song[element];
}
}
best = std::max(best,dp(song,cd,n,k,element + 1));
return dpt[ cd[0] ][ cd[1] ][ cd[2] ][element] = best;
}
int main(void){
int n,k;
std::cin >> n >> k;
int song[n];
for (int i = 0; i < n; ++i) {
std::cin >> song[i];
}
int cd[3] = {0,0,0};
for (int i = 0; i < k; ++i) {
std::cin >> cd[i];
}
memset(dpt, -1 , sizeof(dpt));
std::cout << dp(song, cd, n, k, 0) << "n";
}
This solution takes approximately 1 second with a unknown testbase. But some people got 0 secs. What can I do better here?
Here are some samples:
Input
8 3
7 3 3 2 4 4 2 3
9 8 9
10 1
31 36 16 13 10 13 36 47 1 21
20
10 2
41 8 48 49 33 2 41 26 5 39
22 37
Output
26
17
48
c++ performance dynamic-programming knapsack-problem
edited Dec 18 at 17:06
200_success
128k15150412
asked Nov 6 '15 at 19:22
Felipe
292212
add a comment |
I have a problem were the time in minutes of N songs are given and I have to write the maximum number of time in K CDs.
Input description
The first input line consists of two positive integers N e K ($N le 100$, $K le 3$), which represent respectively the number of songs and te number of cds. The second input line consists of N positive integers, which represent the duration in minutes of each song. The last input line consists of K positive integers, which represent the maximum number of minutes of music that it is possible to record to each cd. No song has more than 50 minutes, and no cd has available more than 50 minutes of space.
Output description
Print a line containing singly the maximum total number of minutes of music that it is possible to record to the cartridges.
To solve this problem I've programmed a dynamic programming solution where the choices are put the $i$th song on each CD or none.
#include <iostream>
#include <algorithm>
#include <string.h>
int dpt[51][51][51][101]; //table for dp
int dp(int *song, int *cd, int n, int k, int element){
if(element == n)
return dpt[ cd[0] ][ cd[1] ][ cd[2] ][element] = 0;
if(dpt[ cd[0] ][ cd[1] ][ cd[2] ][element] != -1)
return dpt[ cd[0] ][ cd[1] ][ cd[2] ][element];
int best = 0;
for (int i = 0; i < k; ++i) {
if(cd[i] >= song[element]){
cd[i] -= song[element];
best = std::max(best,song[element] + dp(song,cd,n,k,element + 1));
cd[i] += song[element];
}
}
best = std::max(best,dp(song,cd,n,k,element + 1));
return dpt[ cd[0] ][ cd[1] ][ cd[2] ][element] = best;
}
int main(void){
int n,k;
std::cin >> n >> k;
int song[n];
for (int i = 0; i < n; ++i) {
std::cin >> song[i];
}
int cd[3] = {0,0,0};
for (int i = 0; i < k; ++i) {
std::cin >> cd[i];
}
memset(dpt, -1 , sizeof(dpt));
std::cout << dp(song, cd, n, k, 0) << "n";
}
This solution takes approximately 1 second with a unknown testbase. But some people got 0 secs. What can I do better here?
Here are some samples:
Input
8 3
7 3 3 2 4 4 2 3
9 8 9
10 1
31 36 16 13 10 13 36 47 1 21
20
10 2
41 8 48 49 33 2 41 26 5 39
22 37
Output
26
17
48
c++ performance dynamic-programming knapsack-problem
edited Dec 18 at 17:06
200_success
128k15150412
asked Nov 6 '15 at 19:22
Felipe
292212
add a comment |
I have a problem were the time in minutes of N songs are given and I have to write the maximum number of time in K CDs.
Input description
The first input line consists of two positive integers N e K ($N le 100$, $K le 3$), which represent respectively the number of songs and te number of cds. The second input line consists of N positive integers, which represent the duration in minutes of each song. The last input line consists of K positive integers, which represent the maximum number of minutes of music that it is possible to record to each cd. No song has more than 50 minutes, and no cd has available more than 50 minutes of space.
Output description
Print a line containing singly the maximum total number of minutes of music that it is possible to record to the cartridges.
To solve this problem I've programmed a dynamic programming solution where the choices are put the $i$th song on each CD or none.
#include <iostream>
#include <algorithm>
#include <string.h>
int dpt[51][51][51][101]; //table for dp
int dp(int *song, int *cd, int n, int k, int element){
if(element == n)
return dpt[ cd[0] ][ cd[1] ][ cd[2] ][element] = 0;
if(dpt[ cd[0] ][ cd[1] ][ cd[2] ][element] != -1)
return dpt[ cd[0] ][ cd[1] ][ cd[2] ][element];
int best = 0;
for (int i = 0; i < k; ++i) {
if(cd[i] >= song[element]){
cd[i] -= song[element];
best = std::max(best,song[element] + dp(song,cd,n,k,element + 1));
cd[i] += song[element];
}
}
best = std::max(best,dp(song,cd,n,k,element + 1));
return dpt[ cd[0] ][ cd[1] ][ cd[2] ][element] = best;
}
int main(void){
int n,k;
std::cin >> n >> k;
int song[n];
for (int i = 0; i < n; ++i) {
std::cin >> song[i];
}
int cd[3] = {0,0,0};
for (int i = 0; i < k; ++i) {
std::cin >> cd[i];
}
memset(dpt, -1 , sizeof(dpt));
std::cout << dp(song, cd, n, k, 0) << "n";
}
This solution takes approximately 1 second with a unknown testbase. But some people got 0 secs. What can I do better here?
Here are some samples:
Input
8 3
7 3 3 2 4 4 2 3
9 8 9
10 1
31 36 16 13 10 13 36 47 1 21
20
10 2
41 8 48 49 33 2 41 26 5 39
22 37
Output
26
17
48
c++ performance dynamic-programming knapsack-problem
edited Dec 18 at 17:06
200_success
128k15150412
asked Nov 6 '15 at 19:22
Felipe
292212
I have a problem were the time in minutes of N songs are given and I have to write the maximum number of time in K CDs.
Input description
The first input line consists of two positive integers N e K ($N le 100$, $K le 3$), which represent respectively the number of songs and te number of cds. The second input line consists of N positive integers, which represent the duration in minutes of each song. The last input line consists of K positive integers, which represent the maximum number of minutes of music that it is possible to record to each cd. No song has more than 50 minutes, and no cd has available more than 50 minutes of space.
Output description
Print a line containing singly the maximum total number of minutes of music that it is possible to record to the cartridges.
To solve this problem I've programmed a dynamic programming solution where the choices are put the $i$th song on each CD or none.
#include <iostream>
#include <algorithm>
#include <string.h>
int dpt[51][51][51][101]; //table for dp
int dp(int *song, int *cd, int n, int k, int element){
if(element == n)
return dpt[ cd[0] ][ cd[1] ][ cd[2] ][element] = 0;
if(dpt[ cd[0] ][ cd[1] ][ cd[2] ][element] != -1)
return dpt[ cd[0] ][ cd[1] ][ cd[2] ][element];
int best = 0;
for (int i = 0; i < k; ++i) {
if(cd[i] >= song[element]){
cd[i] -= song[element];
best = std::max(best,song[element] + dp(song,cd,n,k,element + 1));
cd[i] += song[element];
}
}
best = std::max(best,dp(song,cd,n,k,element + 1));
return dpt[ cd[0] ][ cd[1] ][ cd[2] ][element] = best;
}
int main(void){
int n,k;
std::cin >> n >> k;
int song[n];
for (int i = 0; i < n; ++i) {
std::cin >> song[i];
}
int cd[3] = {0,0,0};
for (int i = 0; i < k; ++i) {
std::cin >> cd[i];
}
memset(dpt, -1 , sizeof(dpt));
std::cout << dp(song, cd, n, k, 0) << "n";
}
This solution takes approximately 1 second with a unknown testbase. But some people got 0 secs. What can I do better here?
Here are some samples:
Input
8 3
7 3 3 2 4 4 2 3
9 8 9
10 1
31 36 16 13 10 13 36 47 1 21
20
10 2
41 8 48 49 33 2 41 26 5 39
22 37
Output
26
17
48
c++ performance dynamic-programming knapsack-problem
c++ performance dynamic-programming knapsack-problem
edited Dec 18 at 17:06
200_success
128k15150412
asked Nov 6 '15 at 19:22
Felipe
292212
edited Dec 18 at 17:06
200_success
128k15150412
asked Nov 6 '15 at 19:22
Felipe
292212
edited Dec 18 at 17:06
200_success
128k15150412
edited Dec 18 at 17:06
200_success
128k15150412
edited Dec 18 at 17:06
200_success
128k15150412
128k15150412
asked Nov 6 '15 at 19:22
Felipe
292212
asked Nov 6 '15 at 19:22
Felipe
292212
asked Nov 6 '15 at 19:22
Felipe
292212
292212
add a comment |
add a comment |
active
oldest
votes
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["\$", "\$"]]);
});
});
}, "mathjax-editing");
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: "196"
};
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: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
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%2fcodereview.stackexchange.com%2fquestions%2f110050%2fmultiple-0-1-knapsack%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
active
oldest
votes
active
oldest
votes
active
oldest
votes
active
oldest
votes
Thanks for contributing an answer to Code Review Stack Exchange!
- 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.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- 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%2fcodereview.stackexchange.com%2fquestions%2f110050%2fmultiple-0-1-knapsack%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
