編程到底難在哪里？
來源：?？?華為機考-HJ28素數(shù)伴侶
點擊上方"互聯(lián)網(wǎng)求職達人"，選擇"設為置頂or星標"
第一時間獲取最實用的求職以及備考信息
?
HJ28素數(shù)伴侶
題目描述：
王強決定把年終獎用于購物，他把想買的物品分為兩類：主件與附件，附件是從屬于某個主件的。如果要買歸類為附件的物品，必須先買該附件所屬的主件，且每件物品只能購買一次。每個主件可以有 0 個、 1 個或 2 個附件。附件不再有從屬于自己的附件。王強查到了每件物品的價格（都是 10 元的整數(shù)倍），而他只有 N 元的預算。除此之外，他給每件物品規(guī)定了一個重要度，用整數(shù) 1 ~ 5 表示。他希望在花費不超過 N 元的前提下，使自己的滿意度達到最大。滿意度是指所購買的每件物品的價格與重要度的乘積的總和。
輸入描述：
輸入的第 1 行，為兩個正整數(shù)N，m，用一個空格隔開：（其中 N （ N<32000 ）表示總錢數(shù)， m （m <60 ）為可購買的物品的個數(shù)。） 從第 2 行到第 m+1 行，第 j 行給出了編號為 j-1 的物品的基本數(shù)據(jù)，每行有 3 個非負整數(shù)?v p q （其中 v 表示該物品的價格（ v<10000 ）， p 表示該物品的重要度（ 1 ~ 5 ）， q 表示該物品是主件還是附件。如果 q=0 ，表示該物品為主件，如果 q>0 ，表示該物品為附件， q 是所屬主件的編號）
輸出描述：
輸出一個正整數(shù)，為張強可以獲得的最大的滿意度。
示例：
輸入：
1000 5 800 2 0 400 5 1 300 5 1 400 3 0 500 2 0
輸出： 2200
答案：
def main():
? ?N, m = map(int, input().split())
? ?N = N // 10
? ?items = [tuple(map(int, input().split())) for _ in range(m)]
? ?primary, accessory = [], [[] for _ in range(m)]
? ?for i, item in enumerate(items):
? ? ? ?if item[2] == 0:
? ? ? ? ? ?primary.append((item[0] // 10, item[1] * item[0], i))
? ? ? ?else:
? ? ? ? ? ?accessory[item[2] - 1].append((item[0] // 10, item[1] * item[0]))
? ?dp = [0] * (N + 1)
? ?for item in primary:
? ? ? ?for i in range(N, item[0] - 1, -1):
? ? ? ? ? ?dp[i] = max(dp[i], dp[i - item[0]] + item[1])
? ? ? ? ? ?for acc in accessory[item[2]]:
? ? ? ? ? ? ? ?if i >= item[0] + acc[0]:
? ? ? ? ? ? ? ? ? ?dp[i] = max(dp[i], dp[i - item[0] - acc[0]] + item[1] + acc[1])
? ? ? ? ? ? ? ?if len(accessory[item[2]]) > 1:
? ? ? ? ? ? ? ? ? ?acc2 = accessory[item[2]][0] if accessory[item[2]][1] == acc else accessory[item[2]][1]
? ? ? ? ? ? ? ? ? ?if i >= item[0] + acc[0] + acc2[0]:
? ? ? ? ? ? ? ? ? ? ? ?dp[i] = max(dp[i], dp[i - item[0] - acc[0] - acc2[0]] + item[1] + acc[1] + acc2[1])
? ?print(dp[-1])if __name__ == "__main__":
? ?main()
解題思路：
動態(tài)規(guī)劃，先處理物品之間的關系，將附件與主件建立聯(lián)系，然后用0-1背包的方法計算最大滿意度。
這道題目是一個帶有條件約束的背包問題。我們首先需要將主件和附件區(qū)分開來，并將它們的價格和重要度按要求計算。接下來，我們將使用動態(tài)規(guī)劃解決這個問題。
將輸入的物品數(shù)據(jù)分成兩個部分：主件和附件。主件是附件所依賴的物品，附件是與主件相關的物品。我們用一個主件列表存儲所有主件的價格、重要度乘積和索引。同時，我們使用一個二維列表存儲每個主件的附件。
初始化一個長度為 N//10+1 的動態(tài)規(guī)劃數(shù)組 dp，其中 N 為總錢數(shù)。這里我們將所有物品的價格除以 10，以簡化計算。數(shù)組 dp 用于存儲在不同預算下所能獲得的最大滿意度。
遍歷所有主件，對于每一個主件，我們需要分別考慮以下情況：
只購買主件，不購買附件。更新 dp 數(shù)組，將當前預算下的滿意度與購買主件后的滿意度進行比較，取較大值。
購買主件和一個附件。遍歷每一個附件，更新 dp 數(shù)組，將當前預算下的滿意度與購買主件及附件后的滿意度進行比較，取較大值。
購買主件和兩個附件。遍歷所有附件組合，更新 dp 數(shù)組，將當前預算下的滿意度與購買主件及兩個附件后的滿意度進行比較，取較大值。
最后，dp 數(shù)組的最后一個元素就是我們要求的最大滿意度。
通過這個思路，我們可以解決這個帶有條件約束的背包問題。
對于正在準備機考的小伙伴，以下是一些建議：
扎實的編程基礎：熟練掌握至少一種編程語言，掌握基本的語法和編程規(guī)范。同時，要熟悉常用的數(shù)據(jù)結構和算法。
練習經(jīng)典題目：在LeetCode、?？途W(wǎng)等在線編程平臺上練習經(jīng)典的編程題目，提高解題速度和準確率。
熟悉輸入輸出格式：熟悉不同編程題目的輸入輸出格式，尤其是一些特定的輸入輸出要求，如ACM模式等。
提高調(diào)試能力：在解題過程中，遇到問題要學會獨立調(diào)試，掌握使用調(diào)試工具的方法，提高代碼質(zhì)量。
時間管理：在機考過程中，合理分配時間，先解決自己擅長的題目，提高通過率。
學習解題技巧：多參考一些編程書籍和教程，學習不同類型題目的解題技巧和方法，提高解題能力。
復習計算機基礎知識：復習計算機基礎知識，如操作系統(tǒng)、計算機網(wǎng)絡、數(shù)據(jù)庫等，這些知識在機考中也可能會涉及。
模擬考試：在準備過程中，進行模擬考試，模擬真實的考試環(huán)境，提高自己的適應能力。
保持良好的心態(tài)：在面對機考時，保持良好的心態(tài)，遇到困難不要慌張，冷靜分析，相信自己的實力。
及時總結和反思：在練習和考試過程中，要及時總結自己的不足和錯誤，進行反思和改進，不斷提高自己的能力。
