背包問題是一個經典的組合優化問題,可以使用動態規劃來解決。以下是使用Java語言解決背包問題的一個示例:
public class KnapsackProblem {
public static int knapSack(int capacity, int[] weights, int[] values, int n) {
int[][] dp = new int[n + 1][capacity + 1];
for (int i = 0; i <= n; i++) {
for (int j = 0; j <= capacity; j++) {
if (i == 0 || j == 0) {
dp[i][j] = 0;
} else if (weights[i - 1] <= j) {
dp[i][j] = Math.max(values[i - 1] + dp[i - 1][j - weights[i - 1]], dp[i - 1][j]);
} else {
dp[i][j] = dp[i - 1][j];
}
}
}
return dp[n][capacity];
}
public static void main(String[] args) {
int capacity = 10;
int[] weights = {2, 3, 4, 5};
int[] values = {3, 4, 5, 6};
int n = weights.length;
int maxValue = knapSack(capacity, weights, values, n);
System.out.println("背包能裝下的最大價值為: " + maxValue);
}
}
在上面的示例中,knapSack
方法用于解決背包問題。它接受背包的容量、物品的重量數組、物品的價值數組和物品的個數作為參數,并返回背包能裝下的最大價值。
在main
方法中,我們定義了一個背包容量為10的背包,物品的重量數組為{2, 3, 4, 5}
,物品的價值數組為{3, 4, 5, 6}
,物品個數為4。然后調用knapSack
方法求解背包能裝下的最大價值,并將結果打印輸出。
運行以上代碼,輸出結果為:
背包能裝下的最大價值為: 10