Как решить эту проблему с помощью подхода Dynamic Programming Top Down?

Question

Я пытаюсь решить проблему с Codeforces (http://codeforces.com/problemset/problem/189/A) Вот постановка задачи:

Поликарп имеет ленту, ее длина равна п. Он хочет разрезать ленту таким образом, чтобы она выполняла следующие два условия:

После резки каждая ленточная деталь должна иметь длину a, b или c. После резки количество деталей ленты должно быть максимально. Помогите Polycarpus и найдите количество частей ленты после требуемой резки .

Ввод Первая строка содержит четыре целых числа, разделенные пробелами n, a, b и c (1 ≤ n, a, b, c ≤ 4000) - длина исходной ленты и допустимые длины элементов ленты после резки, соответственно. Числа a, b и c могут совпадать.

Выход Распечатайте единственное число - максимально возможное количество элементов ленты. Гарантируется, что существует по крайней мере одна правильная режущая лента.

Пример ввод

Пример вывод

Я попытался решить эту проблему с помощью динамического программирования (Перевернутый подхода). Но я не могу получить правильный ответ. Возможно, что-то не так с рекурсивной функцией. Вот мой код:

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

Вы должны проверять на максимум различных val с полученным для различных вариантов выбора i ,

Неправильное Расторжение

Если длина не 0 и не лента не может быть разрезана, вы должны вернуть что-то вроде минус бесконечности. Вы в настоящее время возвращаете m, который изначально -1 (подробнее об этом позже). Это неправильно, и для длинных лент по существу убедитесь, что вы просто выбираете минимум a, b и c.

Использование Globals

Некоторые глобалы, например, 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("%d\n", 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; 
    } 

Просто у каждой суммы [я], мы максимизация количества сокращений. Итак, в сумме [i] мы сохраняем max (sum [i-a] +1, sum [i-b] +1, sum [i-c] +1). Кроме этого, есть только связанные проверки.