洛谷--P1049 装箱问题
程序员文章站
2024-02-29 16:52:52
...
——————————————————————————————————————————————————
0-1背包问题
状态定义:
dp[i][j] 表示只考虑前 i 个物品,物品总体积 <= j 的情况下,装的最大体积是多少
dp[i][j]怎么来呢?来自两种情况:
1.不选择第 i 个物品
dp[i][j] = dp[i - 1][j]
2.选择第 i 个物品
dp[i][j] = dp[i - 1][j - v[i]] + v[i] // 选第 i 个,体积上限就要从前 i-1 个物品中留出 i 的体积,再加上 i 的体积
dp的初始化,dp[i][0] = 0,dp[0][j] = 0
import java.util.Scanner;
public class Main {
static int V;
static int n;
static int[] a;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
V = sc.nextInt();
n = sc.nextInt();
a = new int[n + 1];
for(int i = 1;i <= n;i++) a[i] = sc.nextInt();
sc.close();
int[][] dp = new int[n + 1][V + 1];
for(int i = 1;i <= n;i++) {//递推每件物品
for(int j = 0;j <= V;j++) {//递推每个体积
dp[i][j] = dp[i - 1][j];//不选第i件物品
//选第i件
if(j >= a[i]) dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - a[i]] + a[i]);
}
}
System.out.println(V - dp[n][V]);
}
}