算法具有2個限制的揹包

Question

如果一直在進行一個項目，我遇到以下情形： 需要從一組M中選擇N = 2個框，而M> N的權重總和最好，但有2個限制：

• 我們無法選擇相同的框顏色
• 我們無法選擇相同的方塊ID

箱子自帶的頂部

最高的權重排序0

我選擇（RED1，請分享幫助）與樸素算法開始權重最高RED1，我們無法添加藍天，因爲我們有相同的ID 1，並且不可能添加RED2以及因爲我們有紅色盒子在10的權重下，我們以11的總權重結束，但如果我們選擇Blue1，我們可以以18.9結束Red2 N可以大於2.

這是一個NP難題嗎？ 更好的運行時間效率的解決方案嗎？

Answer 1

我們可以用複雜O(2^color * 2^id * M * N)或回溯+修剪使用DP解決方案的複雜O(M choose N)

所以它取決於有多大的約束爲M，N，顏色和編號。