当前位置:网站首页>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])
边栏推荐
- Is it difficult for an information system project manager?
- The digital economy has broken through the waves. Is Ltd a Web3.0 website with independent rights and interests?
- Yunxiaoduo software internal test distribution test platform description document
- [C language syntax] the difference between typedef struct and struct
- [happy Spring Festival] if you feel happy, dance
- Implementation of linked list in address book management system
- (column 22) typical column questions of C language: delete the specified letters in the string.
- Anti shake and throttling are easy to understand
- ArcGIS应用基础4 专题图的制作
- [SQL Server Express Way] - authentification et création et gestion de comptes utilisateurs
猜你喜欢
Raised a kitten
【经验】win11上安装visio
Web service connector: Servlet
HCIA复习
【SQL server速成之路】——身份驗證及建立和管理用戶賬戶
Embedded interview questions (IV. common algorithms)
Classes and objects (I) detailed explanation of this pointer
Sequoiadb Lake warehouse integrated distributed database, June 2022 issue
MIT6.s081-2020 Lab2 System Calls
C language bubble sort
随机推荐
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
数字经济破浪而来 ,LTD是权益独立的Web3.0网站?
J'ai un chaton.
B站刘二大人-Softmx分类器及MNIST实现-Lecture 9
Network protocol model
H3C S5820V2_5830V2交换机IRF2堆叠后升级方法
How to download GB files from Google cloud hard disk
华为BFD的配置规范
Some easy-to-use tools make your essay style more elegant
Demander le Code de texte standard correspondant à un centre de travail dans l'ordre de production
Novice entry SCM must understand those things
Web Security (V) what is a session? Why do I need a session?
Station B, Master Liu Er - dataset and data loading
Station B Liu Erden - linear regression and gradient descent
Implementation of linked list in address book management system
Memory and stack related concepts
The digital economy has broken through the waves. Is Ltd a Web3.0 website with independent rights and interests?
华为路由器忘记密码怎么恢复
LeetCode_ String inversion_ Simple_ 557. Reverse word III in string
Rustdesk builds its own remote desktop relay server