algorithm - 对于给定长度 n 的色带，如何最大化色带片的数量？

Question

我有一条丝带，它的长度是n。我想以满足以下两个条件的方式剪彩:

1. After the cutting each ribbon piece should have length a, b or c.
2. After the cutting the number of ribbon pieces should be maximum.

找出所需切割后的最大件数。

输入的格式为 n,a,b,c，其中 n 是色带的原始长度，a,b,c 是色带的所需长度。

For eg: I/P = 5 5 3 2
O/P = 2

现在，我能够意识到这应该遵循 DP 解决方案。一维 DP，其中 dp[n] 表示长度为 n 的色带的最大路径数。

现在，我不确定递归关系是否具有以下形式，

dp[n] = dp[n-a] + a;
dp[n] = dp[n-b] + b;
dp[n] = dp[n-c] + c;

这是正确的还是有其他方法？

编辑:根据第一篇文章实现:

#include <iostream>
#include <cmath>
using namespace std;

int dp[100000];
int maxi (int a,int b,int c);
int main (void)
{
    int n,a,b,c;
    cin>>n>>a>>b>>c;
    for (int i = 0; i <= n; i++)
    {
        if ( i == 0 )
            dp[i] = 0;
        else
            dp[i] = maxi(dp[i-a],dp[i-b],dp[i-c])+1;
    }
    cout<<dp[n]<<"\n";
    return 0;
}

int maxi (int a,int b,int c)
{
    int ret;
    if ( a > b )
        ret = a;
    else 
        ret = b;
    if ( ret < c )
        ret = c;
    return ret;
}

Answer 1

if n < 0:
    dp[n] = -infinity
if n == 0:
    dp[n] = 0
if n > 0:
    dp[n] = 1 + max(dp[n-a], dp[n-b], dp[n-c])