CODEWITHSUNDEEP
c++algorithmdynamic-programming
Scott
Scott

Reputation: 77

How do I solve this p‌r‌o‌b‌l‌e‌m using Dynamic Programming Top Down approach?

I'm trying to solve a problem from Codeforces (http://codeforces.com/problemset/problem/189/A) Here's the problem statement:

Polycarpus has a ribbon, its length is n. He wants to cut the ribbon in a way that fulfils the following two conditions:

After the cutting each ribbon piece should have length a, b or c. After the cutting the number of ribbon pieces should be maximum. Help Polycarpus and find the number of ribbon pieces after the required cutting.

Input The first line contains four space-separated integers n, a, b and c (1 ≤ n, a, b, c ≤ 4000) — the length of the original ribbon and the acceptable lengths of the ribbon pieces after the cutting, correspondingly. The numbers a, b and c can coincide.

Output Print a single number — the maximum possible number of ribbon pieces. It is guaranteed that at least one correct ribbon cutting exists.

Sample Input

5 5 3 2

Sample Output

2

I tried to solve this problem using Dynamic Programming (Topdown approach). But I'm not able to get the correct answer. There might be something wrong with the recursive function. Here's my code: 

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

int n,s;
int a[3];
int val,m=-1;
int dp(int n)
{
    if(n==0)
        return 0;
    for(int i=0;i<3;i++)
    {
        if(n>=a[i])
        {
            val=1+dp(n-a[i]);
        }
    }
    if(val>m)
        m=val;
    return m;
}

int main()
{
    scanf("%d %d %d %d",&n,&a[0],&a[1],&a[2]);
    cout<<dp(n)<<endl;
    return 0;
}

What is the problem in the above approach?

Upvotes: 2

Views: 4022

Answers (4)

bhasky
bhasky

Reputation: 11

you can solve this problem through top down approach.A dp problem always check all the possible cases then gives us the optimal solution.so here is the code

#include<bits/stdc++.h>
using namespace std;
int a,b,c;
int DP[4001];
int solve(int n){
if(n == 0)return 0;
if(n<0) return INT_MIN;
if(DP[n] != -1)return DP[n];
else{
   DP[n] = max(1+solve(n-a),max(1+solve(n-b),1+solve(n-c)));
return DP[n];
}
}
int main(){
int n,x;
cin>>n>>a>>b>>c;
for(int i = 0;i<4001;++i){
DP[i] = -1;
}
x = solve(n);
cout<<x;
}

Upvotes: 0

code_master5
code_master5

Reputation: 801

@Ami Tavory correctly suggested the problems with your recursive approach. May be my solution below can help you understand better how to form states and check bounds:

    int main()
    {
            int n, a, b, c;
            cin >> n >> a >> b >> c; 

            const int l = n + 1;
            int sum[l];
            fill(sum, sum+l, INT_MIN);
            sum[0] = 0;

            for(int i=1; i<=n; i++)
            {
                    if(i - a >= 0)
                    {
                            sum[i] = sum[i-a] + 1;
                    }
                    if(i - b >= 0 && sum[i-b] + 1 > sum[i])
                    {
                            sum[i] = sum[i-b] + 1;
                    }
                    if(i - c >= 0 && sum[i-c] + 1 > sum[i])
                    {
                            sum[i] = sum[i-c] + 1;
                    }

            }
            cout << sum[n] << endl;
            return 0;
    }

Simply at each sum[i], we are maximizing the number of cuts. So, at sum[i], we are storing the max(sum[i-a]+1, sum[i-b]+1, sum[i-c]+1). Other than this, there are just bound checks.

Upvotes: 0

sad
sad

Reputation: 820

int main() {
 int n, a, b, c;
 scanf("%d %d %d %d", &n, &cuts[0], &cuts[1], &cuts[2]);
 sort(cuts, cuts + 3);
 for (int i = 0; i <= n; i++) {
    max_cuts[i] = INT_MIN;
 }

 max_cuts[0] = 0;
 max_cuts[cuts[0]] = 1;
 max_cuts[cuts[1]] = 1;
 max_cuts[cuts[2]] = 1;

 for (int i = 1; i <= n; i++) {
    for (int j = 0; j < 3; j++) {
        if (cuts[j] > i) break;
        max_cuts[i] = max(max_cuts[i - cuts[j]] + 1, max_cuts[i]);
    }
 }
 printf("%d\n", max_cuts[n]);
 return 0;
}

Upvotes: 1

Ami Tavory
Ami Tavory

Reputation: 76386

There are several problems:

Wrong Search

In your lines

for(int i=0;i<3;i++)
{
    if(n>=a[i])
    {
        val=1+dp(n-a[i]);
    }
}
if(val>m)
    m=val;

You should be checking for the maximum of the different vals obtained for the different choices of i.

Wrong Termination

If the length is not 0 and no ribbon can be cut, you should return something like minus infinity. You currently return m which is initially -1 (more on this later). This is wrong, and for long ribbons will essentially ensure that you just choose the minimum of a, b, and c.

Use of Globals

Some globals, e.g., m are initialized once but are modified by the recursion. It's not "just" bad programming habits - it's not doing what you want.

No Reuse

By calling the recursion unconditionally, and not reusing previous calls, your running time is needlessly high.

Upvotes: 4

Related Questions