当前位置:网站首页>Dynamic programming -- knapsack problem
Dynamic programming -- knapsack problem
2022-07-06 05:53:00 【Lin Shiliu should work hard】
f[i][j] Once upon a time i A selection of items , The volume is not greater than j Maximum value of
1. 01 knapsack
int f[N][M];
int dp()
{
for(int i=1;i<=n;i++)
for(int j=0;j<=m;j++)
{
f[i][j]=f[i-1][j];
if(j>=v[i])
f[i][j]=max(f[i][j],f[i-1][j-v[i]]+w[i]);
}
return f[n][m];
}
int f[M];
int dp()
{
for(int i=0;i<=n;i++)
for(int j=m;j>=v[i];j--)
f[j]=max(f[j],f[j-v[i]]+w[i]);
return f[m];
}
2. Completely backpack
Completely backpacking Same layer status to update , Compress to One dimensional positive sequence update
int f[N][M];
int dp()
{
for(int i=1;i<=n;i++)
for(int j=0;j<=m;j++)
{
f[i][j]=f[i-1][j];
if(j>=v[i])
边栏推荐
- YYGH-11-定时统计
- After the project is released, index Html is cached
- Demander le Code de texte standard correspondant à un centre de travail dans l'ordre de production
- Text classification still stays at Bert? The dual contrast learning framework is too strong
- High quality coding tool clion
- Some easy-to-use tools make your essay style more elegant
- Classes and objects (I) detailed explanation of this pointer
- 华为路由器忘记密码怎么恢复
- 实践分享:如何安全快速地从 Centos迁移到openEuler
- [JVM] [Chapter 17] [garbage collector]
猜你喜欢
B站刘二大人-反向传播
【课程笔记】编译原理
Rustdesk builds its own remote desktop relay server
59. Spiral matrix
CoDeSys note 2: set coil and reset coil
PDK工艺库安装-CSMC
[force buckle]43 String multiplication
[Baiwen smart home] first day of the course_ Learn Embedded and understand the development mode of bare metal and RTOS
The usage and difference between strlen and sizeof
High quality coding tool clion
随机推荐
Wib3.0 leapfrogging, in leapfrogging (ง • ̀_•́) ง
PDK工艺库安装-CSMC
MIT6.s081-2020 Lab2 System Calls
The ECU of 21 Audi q5l 45tfsi brushes is upgraded to master special adjustment, and the horsepower is safely and stably increased to 305 horsepower
26file filter anonymous inner class and lambda optimization
初识数据库
[force buckle]43 String multiplication
Closure, decorator
入侵检测领域数据集总结
Construction of yolox based on paste framework
59. Spiral matrix
The usage and difference between strlen and sizeof
Application Security Series 37: log injection
Quantitative description of ANC noise reduction
养了只小猫咪
Mysql database master-slave cluster construction
[email protected]树莓派
LAN communication process in the same network segment
[experience] when ultralso makes a startup disk, there is an error: the disk / image capacity is too small
Go language -- language constants