給定長度和位數，我們必須找到可以製作的最小和最大數量？

正如問題所述，我們給出了一個正整數M和一個非負整數S。我們必須找到長度爲M和數字總和S中最小和最大的數字。給定長度和位數，我們必須找到可以製作的最小和最大數量？

限制條件：

（S> = 0和S < = 900）

（M> = 1和M < = 100）

我考慮它和來到結論它必須是動態編程。但是我未能建立DP狀態。

這是我想： -

DP [i] [j] =第一個 '我' 有和 'J' 數字

，並設法使program.This是怎麼它看起來像

/* 
    *** PATIENCE ABOVE PERFECTION *** 
    "When in doubt, use brute force. :D" 

    -Founder of alloj.wordpress.com

#include<bits/stdc++.h> 

using namespace std; 

#define pb push_back 

#define mp make_pair 

#define nline cout<<"\n" 

#define fast ios_base::sync_with_stdio(false),cin.tie(0) 

#define ull unsigned long long int 

#define ll long long int 

#define pii pair<int,int> 

#define MAXX 100009 

#define fr(a,b,i) for(int i=a;i<b;i++) 

vector<int>G[MAXX]; 


int main() 
{ 
    int m,s; 

    cin>>m>>s; 

    int dp[m+1][s+1]; 

    fr(1,m+1,i) 

    fr(1,s+1,j) 

     fr(0,10,k) 
      dp[i][j]=min(dp[i-1][j-k]+k,dp[i][j]); //Tried for Minimum 

    cout<<dp[m][s]<<endl; 

    return 0; 
}

請指導我關於這個DP狀態以及程序的時間複雜度。這是我第一次嘗試DP。

來源

2015-07-22 bitshiftleft

這裏閱讀更多關於它不需要DP，它的貪心算法 – Herokiller

正是貪婪這裏是一個更好的辦法，只要找到與這個屬性的數量和越來越多的數字或遞減排序。 –

-1

DP狀態是（i，j）。它可以被認爲是根據重現定義的數學函數的參數（較小的問題，因此子問題！）

更深入的，狀態通常是唯一識別問題的參數的數目，這樣我們總是知道我們在計算什麼！

讓我們看看你的問題的例子僅

只是爲了確定您的問題，我們需要的位數中可以用這些數字（所形成的狀態+和的注意：你是友善的集體保持總和，而遍歷數字！）

我認爲這是足夠的狀態部分。

現在，

動態編程的運行時間非常簡單。

首先，讓我們看看有多少次在一個問題中存在的問題：

您需要填寫每一個狀態，即你必須覆蓋所有小於或等於整個問題的唯一子的問題！哪個問題比其他問題更爲複雜的關係是已知的！

例如： Fibonacci序列

F(n)=F(n-1)+F(n-2)

注基的情況下，總是最小的子問題!!。注意這裏對於F（n）我們必須計算F（n-1）和F（n-2），並且它將達到n = 1的階段，您需要返回基本情況！因此，子問題的總數可以說是基礎案例和當前問題之間的所有問題！

現在，自下而上，我們需要在這個基本情況和問題之間處理每個狀態的大小。

現在，這告訴我們，運行時間應該是

O（子問題的數量*每每個子問題的時間）。

那麼有多少子問題的解決方案存在DP [0] [0]到DP [M] [S] 併爲每一個問題你正在運行10

O（M * S的環（ Subproblems）* 10）

砍掉那個常數！但它不一定總是一個常數！

這裏有一些你可能想看的代碼！隨意問任何事情！

#include<bits/stdc++.h> 
using namespace std; 
bool DP[9][101]; 
int Number[9][101]; 
int main() 
{ 
    DP[0][0]=true; // It is possible to form 0 using NULL digits!! 
    int N=9,S=100,i,j,k; 
    for(i=1;i<=9;++i) 
     for(j=0;j<=100;++j) 
     { 
      if(DP[i-1][j]) 
      { 
       for(k=0;k<=9;++k) 
        if(j+k<=100) 
         { 
          DP[i][j+k]=true; 
          Number[i][j+k]=Number[i-1][j]*10+k; 
         } 
      } 
     } 
    cout<<Number[9][81]<<"\n"; 
    return 0; 
}

因爲您的約束很高，您可以使用回溯而不是直接存儲數字！

DP[i][j]表示是否可以僅使用i位數字形成數字的總和!!

Number[i][j]

是我的懶惰，以避免輸入一個回溯的方式（困了，其已經上午03點）

我嘗試添加所有可能的數字擴展狀態。

它實質上是一種前鋒DP風格！您可以在Topcoder

來源

2015-07-22 11:41:47

請注意，如果你downvote告訴我的原因加OP已經問最後這個問題而不是問題！ –

謝謝你的努力:)你能請示範我在這個問題中狀態如何。再次感謝 – bitshiftleft

dp [i] [j] =首先'i'數字總和'j'用你的語言直接 –

dp solution goes here :- 

#include<iostream> 


using namespace std; 

int dp[102][902][2] ; 
void print_ans(int m , int s , int flag){ 
    if(m==0) 
     return ; 
    cout<<dp[m][s][flag]; 
    if(dp[m][s][flag]!=-1) 
     print_ans(m-1 , s-dp[m][s][flag] , flag); 
    return ; 
} 
int main(){ 
    //freopen("problem.in","r",stdin); 
    //freopen("out.txt","w",stdout); 
    //int t; 
    //cin>>t; 
    //while(t--){ 
    int m , s ; 
    cin>>m>>s; 
    if(s==0){ 
     cout<<(m==1?"0 0":"-1 -1"); 
     return 0; 
    } 
    for(int i = 0 ; i <=m ; i++){ 
     for(int j=0 ; j<=s ;j++){ 
      dp[i][j][0]=-1; 
      dp[i][j][1]=-1; 
     } 
    } 
    for(int i = 0 ; i < 10 ; i++){ 
     dp[1][i][0]=i; 
     dp[1][i][1]=i; 
    } 
    for(int i = 2 ; i<=m ; i++){ 
     for(int j = 0 ; j<=s ; j++){ 
      int flag = -1; 
      int f = -1; 
      for(int k = 0 ; k <= 9 ; k++){ 
       if(i==m&&k==0) 
        continue; 
       if(j>=k && flag==-1 && dp[i-1][j-k][0]!=-1) 
        flag = k; 
      } 
      for(int k = 9 ; k >=0 ;k--){ 
       if(i==m&&k==0) 
        continue; 
       if(j>=k && f==-1 && dp[i-1][j-k][1]!=-1) 
        f = k; 
      } 
      dp[i][j][0]=flag; 
      dp[i][j][1]=f; 
     } 
    } 
    if(m!=0){ 
     print_ans(m , s , 0); 
     cout<<" "; 
     print_ans(m,s,1); 
    } 
    else 
     cout<<"-1 -1"; 
     cout<<endl; 
// } 
}

來源

2016-10-18 16:20:52

此處print_ans函數用於打印ans。 –

給定長度和位數，我們必須找到可以製作的最小和最大數量？

回答

相關問題