1
$\begingroup$

I've come across this problem and I can't find a decent DP solution for it.

Given an initial amount of money and a bunch of items to buy (where each item has a 'value' and 'price' assigned to it), maximize the total 'value' such that the money spent does not exceed the initial money. With the exception that if the total money spent exceeded 2000 dollars, the buyer gets a 200 dollar refund card and can spend precisely that much more. For instance, with an initial money of 1900 dollars, you can spend up to 2100 dollars worth of items.

Any help would be appreciated.

I know that this is just the normal 0-1 knapsack problem, but I'm struggling with coding the part where I need to handle the refund card.

This is as far as I got, but it's not giving me the proper answer:

(I've basically filled the normal knapsack memo table in a bottom-up fashion in such manner that for each element at memo[i][w], I've calculated the most amount of "value" gained using precisely "w" money. Only that I added a one-time flag that if the money I've used exceeded 2000, add 200 dollars to my "reminder" money so "w" iterates up to "original money + 200".)

include <bits/stdc++.h>
using namespace std;

int memo[100][10200], favor[100], price[100];
int totalMoney, itemNum;
int solve(int rem, int idx)
{
    int w;
    bool flag_once = false;
    for (int i = 0; i <= idx; i++)
    {
        for (w = 0; w <= rem; w++)
        {
            if (totalMoney - (w - price[i - 1]) > 2000 && !flag_once)
            {
                rem += 200;
                flag_once = true;
            }
            if (i == 0 || w == 0)
            {
                memo[i][w] = 0;
            }
            else if (price[i - 1] <= w)
            {
                memo[i][w] = max(favor[i - 1] + memo[i - 1][w - price[i - 1]], memo[i - 1][w]);
            }
            else
            {
                memo[i][w] = memo[i - 1][w];
            }
        }
    }
    return memo[idx][rem];
}

int main()
{
    cin >> totalMoney >> itemNum;
    for (int i = 0; i < itemNum; i++)
    {
        cin >> price[i] >> favor[i];
    }
    cout << solve(totalMoney, itemNum) << endl;
}
$\endgroup$
  • $\begingroup$ Asking about your specific implementation on C++ is unfortunately off-topic here. Could you describe your algorithm in natural language or in pseudo-code? This would make it easier for us to answer your question. Thanks. $\endgroup$ – Discrete lizard Apr 15 '18 at 10:49
  • $\begingroup$ @Discretelizard Why of course! I've basically filled the normal knapsack memo table in a bottom-up fashion in such manner that for each element at memo[i][w], I've calculated the most amount of "value" gained using precisely "w" money. Only that I added a one-time flag that if the money I've used exceeded 2000, add 200 dollars to my "reminder" money so "w" iterates up to "original money + 200". If there's anything more I need to elaborate on I'd more than glad to. $\endgroup$ – Arian Tashakkor Apr 15 '18 at 14:16
  • $\begingroup$ Good. It would be best if you edit your question to contain that information, as it is then better visible (and better formatted) for future visitors. Try to make the edit as if it were your original post (that is, no need to preface anything with "edit" or be afraid to remove things), as we keep a history of all versions. $\endgroup$ – Discrete lizard Apr 15 '18 at 14:43
  • $\begingroup$ I don't think that figuring out how to code up the standard dynamic programming algorithm for 0-1 knapsack is suitable here. Coding questions are off-topic here. $\endgroup$ – D.W. Apr 16 '18 at 3:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.