一、背包模型
有一个体积为V的背包,商店有n个物品,每个物品有一个价值v和体积w,每个物品只能被拿一次,问能够装下物品的最大价值。
这里每一种物品只有两种状态即"拿"或"不拿".
设状态dp[i][j]表示到第i个物品为止,拿的物品总体积为j的情况下的最大价值。
并不关心某个物品有没有被拿,只关心当前体积下的最大价值。
转移方程为:dp[i][j]=max(dp[i-1][j],dp[i-1][j-w]+v);如果不拿物品i,那么最大价值就是dp[i-1][j],如果拿了就是从体积j-v转移过来,体积会变大w,价值增加v。
最后输出dp[n][v];
例题---小明的背包1
https://www.lanqiao.cn/problems/1174/learning/
小明有一个容量为V的背包。这天他去商场购物,商场一共有N件物品,第i件物品的体积为,价值为。
小明想知道在购买的物品总体积不超过V的情况下所能获得的最大价值为多少,请你帮他算算。
输入描述:输入第1行包含两个正整数N,V,表示商场物品的数量和小明的背包容量。
第2~N+1行包含2个正整数w,v,表示物品的体积和价值。
1<=N<=。
输出描述:输出一行整数表示小明所能获得的最大价值。
示例:5 20
1 6
2 5
3 8
5 15
3 3 37
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner scan = new Scanner(System.in);
int n = scan.nextInt();// num of things
int weight = scan.nextInt();// the package weight
int v[] = new int[n];// value of thing
int w[] = new int[n];// weight of thing
int dp[][] = new int[n + 1][weight + 1];
for (int i = 0; i < n; i++) {
w[i] = scan.nextInt();
v[i] = scan.nextInt();
}
for (int i = 0; i < n + 1; i++) {
for (int j = 0; j < weight + 1; j++) {
if (i == 0 || j == 0) {
dp[i][j] = 0;
continue;
}
if (j < w[i - 1]) {
dp[i][j]=dp[i-1][j];
}
else {
dp[i][j]=Math.max(dp[i-1][j], v[i-1]+dp[i-1][j-w[i-1]]);
}
}
}
System.out.println(dp[n][weight]);
scan.close();
}
}
2、01背包的优化
例题---背包与魔法
https://www.lanqiao.cn/problems/2223/learning/
小蓝面前有N件物品,其中第i件重量是,价值是