如何使用动态规划自顶向下的方法来解决这个问题?

Question

我试图解决一个问题从Codeforces (http://codeforces.com/problemset/problem/189/A)下面是问题说明:

Polycarpus有一条缎带，它的长度是n。他想以满足以下两个条件的方式切割缎带:

切割后，每个缎带片的长度应为a, b或c。裁切后的丝带条数应达到最大值。帮助Polycarpus找到所需的丝带碎片的数量切割。

输入第一行包含四个空格分隔的整数n, a, b, c(1≤n, a, b, c≤4000)，分别表示原缎带的长度和切割后缎带块的可接受长度。数字a, b和c可以重合。

输出打印单个数字-色带片的最大可能数量。保证至少有一个正确的丝带切割存在。

示例输入

5 3 2

的示例输出2

我尝试用动态规划(自上而下的方法)来解决这个问题。但是我不能得到正确的答案。递归函数可能有问题。下面是我的代码:

#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;
}

上述方法的问题是什么?

Answer 1

有几个问题:

错误搜索

在你的行

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

您应该检查不同i选择所获得的不同val s的最大值。

错误的终止

如果长度不为0并且不能切割带状，则应该返回类似于-∞的值。您目前返回m，最初为-1(稍后将详细介绍)。这是错误的，对于长丝带将确保您只选择a, b和c的最小值。

全局变量的使用

一些全局变量，如m，初始化一次，但被递归修改。这不仅仅是坏的编程习惯——这不是你想要的。

没有重用

通过无条件地调用递归，并且不重用以前的调用，您的运行时间不必要地高。

Answer 2

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("%dn", max_cuts[n]);
 return 0;
}

Answer 3

@Ami Tavory正确地指出了递归方法的问题。也许我下面的解决方案可以帮助你更好地理解如何形成状态和检查边界:

    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;
    }

简单地说，在每个sum[i]处，我们都在最大化切割次数。在sum[i]处，我们存储的是最大值(sum[i-a]+1, sum[i-b]+1, sum[i-c]+1)除此之外，只有绑定支票。

Answer 4

您可以通过自顶向下的方法来解决这个问题。dp问题总是检查所有可能的情况，然后给出最优解。这里是代码

#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;
}