ダイナミックプログラミングに固執

Question

問題を抱えている： ミルクマンは、様々なサイズのパッケージボトルでミルクを提供します。ボトルのサイズは{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; 
} 

私が唯一、すべてのinput.I用出力ゼロdp.Pleaseのヘルプに新しいです取得this.Butのための動的プログラミングを使用していました。

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

私はこれがうまくいけば幸いです