我有一個代碼,該代碼通過背包算法(bin pack NP-hard問題)計算出最佳值:int Knapsack::knapsack(std::vector<Item>& items, int W){ size_t n = items.size(); std::vector<std::vector<int> > dp(W + 1, std::vector<int>(n + 1, 0)); for (size_t j = 1; j <= n; j++) { for ( int w = 1; w <= W; w++) { if (items[j-1].getWeight() <= w) { dp[w][j] = std::max(dp[w][j-1], dp[w - items[j-1].getWeight()][j-1] + items[j-1].getWeight()); } else { dp[w][j] = dp[w][j - 1]; } } } return dp[W][n];}我還需要顯示包裝中包含的元素。我想創建一個數組,在其中添加一個元素。因此,問題在于添加此附加元素的步驟是什么,或者還有其他更有效的方法嗎?問題:我希望能夠知道為我提供最佳解決方案的項目,而不僅僅是最佳解決方案的價值。PS。對不起,我的英語不是我的母語。
添加回答
舉報
0/150
提交
取消
