PTT數位生活區 / Prob_Solve (計算數學 Problem Solving)

Re: [問題] 0～9 挑k個數字, 組出最接近 A 的數字

看板Prob_Solve (計算數學 Problem Solving)作者EdisonX (卡卡獸)時間10年前 (2014/10/31 23:06)推噓2(2推 0噓 6→)

留言8則, 4人參與討論串2/5 (看更多)

※ 引述《ooooooo (感覺銜接最重要...)》之銘言： : 使用以下例子說明題目要求： : input(A, k) , : A 表示目標數字 : k 表示可以使用的 digit 數目 : 補充條件(謝謝 E板友提醒)： : 1 <= A <= 10^15, 1<=k<=10 : Ex1 : Input(8000, 1) : 代表只能使用一種數字，來組成最接近 8000 的數，Output 為 7777 : Ex2 Input(3355798521 , 10) : 10 表示 0～9 均能使用, 故output 為 3355798521 : Ex3 Input(262004, 2) : Output 為： 262222 : 目前是往dp 的方向在思考，不過卡住了，請教板友這題目該怎麼解，謝謝我覺得這題關鍵測資應該是類似 (8000, 1) , (88499 , 2) 假設 input(88499, 2) , 令 input[4:0] = {9,9,4,8,8} , len = 5 虛碼大概如下 dig = 2; // 只能使用 2 位數 use_dig = 0; // 已使用位數 pool[10] = {0}; // 已使用過的數字放進來 int output[10]; // 最後的結果 for(i = len-1 ; i >= 0 ; i--) { // 如果 input[i] 已在 pool 裡使用過的話，直接填入插入 if(TRUE == lookup_exist( input[i] , pool[0:dig] ) ) { output[i] = input[i]; } else // input[i] 沒在 pool 裡使用過 { if( dig - use_dig == 1) break; // 剩最後一位可挑時跳出去 else { output[i] = input[i] ; dig++; } //非最後一位，直接填入 } } if(i < 0) { print( output ) ; // 全挑完, 直接輸出答案 exit } else { // 這裡還有一位可挑 , // 依序挑出 input[i-1], input[i] , input[i+1] 做最後排列， // 看哪個結果比較好 (A) } --------------------- 參考下。目前我想到的算法如上，沒完整 implement 出來, 另外 (A) 部份也沒再細思，但推了下整個流程應是可行的？ -- 「自從我學了 C# , 人都變聰明 , 考試都考一百分」「自從我學了 VB , 皮膚都變好 , 人也變漂亮了」「自從我學了 Java , 明顯變壯 , 個子也變高了」「自從我學了 C++ , 內分泌失調 , 頭都禿了... 」 < Kuso 星爺語錄 > -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 180.177.74.8 ※ 文章網址: http://www.ptt.cc/bbs/Prob_Solve/M.1414767978.A.32B.html ※ 編輯: EdisonX (180.177.74.8), 10/31/2014 23:07:53