застрял в динамическом программировании

Question

У этого проблемы: A Milkman подает молоко в упакованных бутылках разных размеров. Возможный размер бутылок - {1, 5, 7 и 10} литров. Он хочет поставлять необходимое количество, используя как можно меньше бутылок, независимо от их размера. Ваша цель - помочь ему найти минимальное количество бутылок, необходимых для подачи данного спроса на молоко.

вход Формат:

Первая строка содержит количество тестов N Далее N строк, каждая из которых содержит положительное целое число Li, который соответствует требованию молока.

Формат вывода:

Для каждого входа Ли, выведите минимальное количество бутылок, необходимых для удовлетворения спроса

Я написал этот код для этой проблемы.

#include <iostream> 
#include <vector> 
#include <stdio.h> 
#include <set> 
#include <algorithm> 
#include <string> 
#include <queue> 
#include <map> 
#include <iomanip> 
#include <locale> 
#include <stdlib.h> 
#include <cstring> 
#include <cmath> 
#include <tgmath.h> 
using namespace std; 
const int INF = 1000000000; 
int m[4] = { 1, 5, 7, 10 }; 
int r[100000000]; 

int milk(int n) { 
    int q; 

    if (r[n] < INF) 
     return r[n]; 

    if (n <= 0) 
     q = 0; 
    else { 
     q = INF; 
     for (int i = 0; i < 4; i++) { 
      if (n >= m[i]) 
       q = min(q, 1 + milk(n - m[i])); 
     } 
    } 

    r[n] = q; 

    return q; 
} 

int main() { 
    int t, n; 
    cin >> t; 

    while (t--) { 
     cin >> n; 
     memset(r, INF, sizeof(r)); 
     cout << milk(n) << endl; 
    } 

    return` 0; 
} 

Я использовал динамическое программирование для this.But я только получить выход нуля на каждые input.I новичок в dp.Please помощь.

Answer 1

int milk(int n) { 
    int min; 
    memset(r, 0, sizeof(r)); 
    for (int i = 1; i <= n; i++) { 
     min = 10000000; // some very large value greater than n 
     for (j = 0; j <= 3; j++) { 
      if (m[j] > i) 
       continue; 
      else if (r[i - m[j]] < min) 
       min = r[i - m[j]]; 
     } 
     r[i] = min; 
    } 
    return r[n]; 
} 

Надеюсь, это сработает, и это поможет вам, если у вас есть какие-либо сомнения.