当前位置:网站首页>买口罩(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]);
}
}
边栏推荐
- 长沙学院2022暑假训练赛(一)六级阅读
- String.toLowerCase(Locale.ROOT)
- BeautifulSoup4的介绍与使用
- The JVM thread state
- XxlJobConfig分布式定时器任务管理XxlJob配置类,替代
- 输入框最前面添加放大镜&&background-image和background-color冲突问题
- Use of PlantUML plugin in idea
- 细谈VR全景:数字营销时代的宠儿
- SIGINT,SIGKILL,SIGTERM信号区别,各类信号总结
- Altium designer software commonly used the most complete package library, including schematic library, PCB library and 3D model library
猜你喜欢
ByteDance Interview Questions: Mirror Binary Tree 2020
缓存技术使用
ByteDance Written Exam 2020 (Douyin E-commerce)
sql problem solving statement to create a table
Use of PlantUML plugin in idea
C language implements sequential stack and chain queue
05 多线程与高并发 - ThreadPoolExecutor 源码解析
Xilinx Zynq ZynqMP DNA
IQ Products CMV Brite Turbo试剂盒的原理
db.sqlite3 has no "as Data Source" workaround
随机推荐
Silently start over, the first page is also a new page
shardingsphere data sharding configuration item description and example
APP商品详情源数据接口(淘宝/京东/拼多多/苏宁/抖音等平台详情数据分析接口)代码对接教程
2022年7月小结
工控设备的系统如何进行加固
线程的6种状态
当酷雷曼VR直播遇上视频号,会摩擦出怎样的火花?
flask创建数据库失败未报错
逆向工程
SIGINT,SIGKILL,SIGTERM信号区别,各类信号总结
抗菌药物丨Toronto Research Chemicals 天冬酰胺D
idea中PlantUML插件使用
P7阿里面试题2020.07 之滑动窗算法(阿里云面试)
The Integer thread safe
mysql 总结
Service
报错:FSADeprecationWarning: SQLALCHEMY_TRACK_MODIFICATIONS adds significant overhead and will be disab
The water problem of leetcode
workbench 数据导出
C# 利用iTextSharp画PDF