有n个物体,第i个物体的重量为wi(wi为正整数)。选择尽量多的物体,使得总重量不超过C。
时间: 2023-11-12 16:29:04 浏览: 97
这是一个经典的背包问题,可以用动态规划算法来解决。
设f[i][j]表示前i个物体中,选择若干个物体总重量不超过j时的最大价值。则有以下状态转移方程:
f[i][j] = max(f[i-1][j], f[i-1][j-wi] + vi)
其中,wi表示第i个物体的重量,vi表示第i个物体的价值。
初始化时,f[0][j] = 0,表示前0个物体中选择任意个物体总重量不超过j时的最大价值为0。
最终结果为f[n][C],即前n个物体中选择若干个物体总重量不超过C时的最大价值。
以下是Java的代码实现:
```java
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt(); // 物体个数
int C = scanner.nextInt(); // 背包容量
int[] w = new int[n+1]; // 物体重量
int[] v = new int[n+1]; // 物体价值
for (int i = 1; i <= n; i++) {
w[i] = scanner.nextInt();
v[i] = scanner.nextInt();
}
int[][] f = new int[n+1][C+1]; // 状态数组
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= C; j++) {
if (j >= w[i]) {
f[i][j] = Math.max(f[i-1][j], f[i-1][j-w[i]] + v[i]);
} else {
f[i][j] = f[i-1][j];
}
}
}
System.out.println(f[n][C]);
}
}
```
代码实现思路如下:
1. 输入物体个数n和背包容量C;
2. 输入每个物体的重量和价值;
3. 初始化状态数组f,f[0][j] = 0;
4. 根据状态转移方程更新状态数组f;
5. 输出f[n][C],即前n个物体中选择若干个物体总重量不超过C时的最大价值。
时间复杂度为O(nC),空间复杂度为O(nC)。
阅读全文