完全背包问题 java实现 思路
时间: 2023-09-09 10:12:01 浏览: 47
完全背包问题是一种经典的动态规划问题,其思路如下:
1. 定义数组dp[i][j]表示将前i个物品放入容量为j的背包中所获得的最大价值。
2. 初始化dp数组,当容量为0时,最大价值为0;当没有物品可选时,最大价值也为0。
3. 对于每个物品i,从容量为j到背包总容量W遍历,计算将该物品放入背包和不放入背包两种情况下的最大价值。如果将该物品放入背包,则其贡献为v[i],同时需要减去物品重量w[i];如果不放入背包,则最大价值与dp[i-1][j]相同。
4. 更新dp[i][j]为两种情况中的最大值。
5. 最终得到dp[n][W]即为所求。
Java实现代码如下:
```
public static int knapsack(int W, int[] w, int[] v) {
int n = w.length;
int[][] dp = new int[n+1][W+1];
for (int i = 0; i <= n; i++) {
dp[i][0] = 0;
}
for (int j = 0; j <= W; j++) {
dp[0][j] = 0;
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= W; j++) {
if (j >= w[i-1]) {
dp[i][j] = Math.max(dp[i-1][j], dp[i][j-w[i-1]]+v[i-1]);
} else {
dp[i][j] = dp[i-1][j];
}
}
}
return dp[n][W];
}
```
其中W为背包总容量,w和v分别为物品重量和价值的数组。时间复杂度为O(nW),空间复杂度为O(nW)。