背包问题
2026/4/9大约 3 分钟
背包问题
题目
有 N 件物品和一个容量是V 的背包。每件物品只能使用一次。
第 ii 件物品的体积是 vi，价值是 wi。
求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
输出最大价值。
输入格式
第一行两个整数，N,V，用空格隔开，分别表示物品数量和背包容积。
接下来有 N行，每行两个整数 vi,wi，用空格隔开，分别表示第 ii 件物品的体积和价值。
输出格式
输出一个整数，表示最大价值。
数据范围
0<N,V≤10000<N,V≤1000
0<vi,wi≤10000<vi,wi≤1000
输入样例
4 5
1 2
2 4
3 4
4 5输出样例：
8朴素解法(输入输出版)
/**
* @see Acwing 01背包问题 https://www.acwing.com/problem/content/2/
*/
import java.util.Scanner;
public class o1bagIOClass {
static int N = 1010;
static int n,bagVolume;
static int[]volume = new int[N];
static int[]worth = new int[N];
static int[][] dp = new int[N][N];
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n =sc.nextInt();
bagVolume = sc.nextInt();
//一定要注意，输入输出版的背包问题，2个数组都是从第二个数开始填入的
for(int i = 1; i <= n; i++) {
volume[i] = sc.nextInt();
worth[i] = sc.nextInt();
}
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= bagVolume; j++) {
dp[i][j] = dp[i-1][j];
if (j>=volume[i]){
dp[i][j] = Math.max(dp[i][j],dp[i-1][j-volume[i]]+worth[i]);
}
}
}
System.out.println(dp[n ][bagVolume]);
}
}朴素解法(函数版)
import java.util.Scanner;
public class o1bagClass {
public static int o1bagSolution(int[] weight, int[] value, int bagWeight) {
int num = weight.length;
int[][] dp = new int[num + 1][bagWeight + 1];
//注意函数版本的背包；2个数组都是从第一个数开始填入的，所以状态转移方程有所差别
for (int i = 1; i <= num; i++) {
for (int j = 0; j <= bagWeight; j++) {
dp[i][j] = dp[i - 1][j];
if (j >= weight[i - 1]) {
dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weight[i - 1]] + value[i - 1]);
}
}
}
return dp[num][bagWeight];
}
public static void main(String[] args) {
int[] weight ={2,3,4,5};
int[] value = {3,4,5,6};
System.out.println(o1bagSolution(weight,value,8));
}
}空间优化解法(输入输出版)
/**
* @see Acwing 01背包问题 https://www.acwing.com/problem/content/2/
*/
import java.util.Scanner;
public class o1bagOptimizationClass {
/**
* n 为物品的数量
* bagVolume 为背包的体积
* volume[] 存储每个物品的体积
* worth[] 存储每个物品的价值
*/
static int N = 1010;
static int n, bagVolume;
static int[] volume = new int[N];
static int[] worth = new int[N];
static int[] dp = new int[N];
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
bagVolume = sc.nextInt();
//一定要注意，输入输出版的背包问题，2个数组都是从第二个数开始填入的
for (int i = 1; i <= n; i++) {
volume[i] = sc.nextInt();
worth[i] = sc.nextInt();
}
for (int i = 1; i <= n; i++) {
//dp[i][j] = dp[i-1][j];优化过后为恒等式，直接去掉
for (int j = bagVolume; j >= volume[i]; j--) {
//if语句合并入for循环内
//dp[i][j] = Math.max(dp[i][j],dp[i-1][j-volume[i]]+worth[i]);
//优化掉一维后为dp[j] = Math.max(dp[j],dp[j-volume[i]]+worth[i]);
//因为dp[j] 必须比 dp[j-volume[i]] 要后计算出，所以采用倒序遍历
dp[j] = Math.max(dp[j], dp[j - volume[i]] + worth[i]);
}
}
System.out.println(dp[bagVolume]);
}
}空间优化解法(函数版)
import java.util.Scanner;
public class o1bagClass {
public static int o1bagSolutionOptimization
(int[] volume, int[] worth, int bagWeight) {
int num = volume.length;
int[] dp = new int[bagWeight + 1];
for (int i = 1; i <= num; i++) {
for (int j = bagWeight; j >= volume[i - 1]; j--) {
dp[j] = Math.max(dp[j], dp[j - volume[i - 1]] + worth[i - 1]);
}
}
return dp[bagWeight];
}
public static void main(String[] args) {
int[] weight ={2,3,4,5};
int[] value = {3,4,5,6};
System.out.println(o1bagSolutionOptimization(weight,value,8));
}
}代码优化版(边输入边处理)
import java.util.Scanner;
public class o1bagOptimizationPlusIOClass {
static int N = 1010;
static int[] dp = new int[N];
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n =sc.nextInt(), bagVolume = sc.nextInt();
//一定要注意，输入输出版的背包问题，2个数组都是从第二个数开始填入的
for(int i = 1; i <= n; i++) {
int volume,worth;
volume = sc.nextInt(),worth = sc.nextInt();
for (int j = bagVolume; j >=volume ; j--) dp[j] = Math.max(dp[j], dp[j-volume]+worth);
}
System.out.println(dp[bagVolume]);
}
}