生成动态规划java代码
时间: 2023-10-13 09:07:29 浏览: 35
好的,以下是一个简单的背包问题的动态规划Java代码:
```java
public class Knapsack {
public static int knapsack(int[] weights, int[] values, int capacity) {
int n = weights.length;
int[][] dp = new int[n + 1][capacity + 1];
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= capacity; j++) {
if (weights[i - 1] <= j) {
dp[i][j] = Math.max(dp[i - 1][j], values[i - 1] + dp[i - 1][j - weights[i - 1]]);
} else {
dp[i][j] = dp[i - 1][j];
}
}
}
return dp[n][capacity];
}
public static void main(String[] args) {
int[] weights = {10, 20, 30};
int[] values = {60, 100, 120};
int capacity = 50;
System.out.println(knapsack(weights, values, capacity)); // 输出220
}
}
```
以上代码实现了一个背包问题的动态规划算法。其中,weights数组存储了每个物品的重量,values数组存储了每个物品的价值,capacity表示背包的容量。dp数组记录了状态转移过程中的最优解。最终返回dp[n][capacity]即为所求。