auf dynamische Programmierung stecken

Question

Heres das Problem: Ein Milchmann dient Milch in abgepackten Flaschen unterschiedlicher Größe. Die mögliche Größe der Flaschen ist {1, 5, 7 und 10} Liter. Er möchte die gewünschte Menge mit möglichst wenig Flaschen liefern, unabhängig von der Größe. Ihr Ziel ist es, ihm zu helfen, die Mindestanzahl von Flaschen zu finden, die erforderlich sind, um den gegebenen Milchbedarf zu decken.

Eingangsformat:

erste Zeile enthält Anzahl der Testfälle N nächsten N Zeilen enthalten jeweils eine positive ganze Zahl ist, die Li auf die Nachfrage von Milch entspricht.

Ausgabeformat:

Für jeden Eingang Li, drucken Sie die minimale Anzahl von Flaschen benötigt die Nachfrage

ich diesen Code für das Problem geschrieben haben, zu erfüllen.

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

ich verwendet habe, dynamische Programmierung für this.But erhalte ich nur einen Ausgang Null für alle input.I sind hier Hilfe 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]; 
} 

Ich hoffe, das funktioniert und es würde Ihnen helfen, Kommentar, wenn Sie irgendwelche Zweifel haben.