当前位置:网站首页>买口罩(0-1背包)
买口罩(0-1背包)
2022-08-09 06:41:00 【斯沃福德】
题目:
思路: 0-1 背包
背包两个属性:容量W和N个物品(N个数一般等于物品数量,即 状态 i )
限定钱,即钱就是限定的容量W,物品单价就是wt
求最多买多少口罩,即口罩的个数就是val值;
初始化 dp[N+1][W+1],
dp定义:最终所求为 dp[N][W]即对前 i 个物品进行选择,在容量为 w时,可以装的最大价值是 dp[i][w];
basecase:
base case 就是 dp[0][…] = dp[…][0] = 0,即没有物品和没有容量时,背包装的价值为0;但数组会自动初始化为0;
状态: i 为物品序号, w为每种容量;
状态转移:
求以下两种的最大值:
1.不装入 i 物品,dp=dp[i-1][w] ;
2.装入 i 物品,dp=dp[i-1][w-wt[i]]+val[i] ,即前i-1个物品相当于放到了容量为 w - wt[i-1]]的背包里!
import java.util.Scanner;
public class Main{
public static void main(String[] args){
Scanner in=new Scanner(System.in);
int W=in.nextInt();
// 限定了N元,即价格是背包容量
int[] wt={
0,2,2,3,1,5,2};
// 求最多多少口罩,即口罩个数是价值
int[] val={
0,2,3,1,5,4,3};
int n=6;
int[][] dp=new int[n+1][W+1]; // 会初始化为全0
// i=0是base case
for(int p=0;p<=W;p++){
dp[0][p]=0; //没有物品
}
for(int q=0;q<=n;q++){
dp[q][0]=0;//没有容量
}
//
for(int i=1;i<=n;i++){
//遍历每个物品(序号)
for(int w=0;w<=W;w++){
//遍历每种容量大小
if(w<wt[i]){
//当前容量w小于了物品i需要的容量,则一定不放背包
dp[i][w]=dp[i-1][w];
}else{
// 放入和不放入,选最大
dp[i][w]=Math.max( dp[i-1][w] , dp[i-1][w-wt[i]]+val[i]);
}
}
}
System.out.println(dp[n][W]);
}
}
边栏推荐
猜你喜欢
随机推荐
INSTALL_RPATH and BUILD_RPATH problem in CMake
集合内之部原理总结
The solution that does not work and does not take effect after VScode installs ESlint
db.sqlite3没有“as Data Source“解决方法
中英文说明书丨CalBioreagents 醛固酮单克隆抗体
DDD 领域驱动设计
Error: flask: TypeError: 'function' object is not iterable
[HNOI2002]营业额统计
单例模式
直接用的zip包 缺少很多依赖,pip没有,感觉用anaconda create一个环境会方便点
IQ Products巨细胞病毒CMV感染检测试剂盒的特征和应用
物理层课后作业
工控设备的系统如何进行加固
crc计算
After the VB.net program is closed, the background is still connected to SQL
longest substring without repeating characters
普罗米修斯原理及节点发布
io.lettuce.core.RedisCommandTimeoutException Command timed out
2022.8.8DAY628
IQ Products CMV Brite Turbo试剂盒的原理