当前位置:网站首页>On the inverse order problem of 01 knapsack problem in one-dimensional state
On the inverse order problem of 01 knapsack problem in one-dimensional state
2022-07-06 08:29:00 【@Positive_ function】
I hope my explanation below will be helpful to you
Classic title
Topic link :
2. 01 knapsack problem - AcWing Question bank
I like this algorithm platform very much , It is recommended that you can go to the above to learn algorithms
Title Description :
2. 01 knapsack problem
Yes N Items and a capacity are V The backpack . Each item can only be used once .
The first i The volume of the item is vi, The value is wi.
Find out which items to pack in your backpack , The total volume of these items can not exceed the capacity of the backpack , And the total value is the greatest .
Output maximum value .
I won't specifically talk about the two-dimensional approach here , If you are not very clear about the two-dimensional approach , Then you can search on the Internet , The focus here is on why the cycle should be in reverse order
Two dimensional approach :
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 1010;
int f[N][N];
int w[N],v[N];
int n,m;
int main(){
cin >> n >> m;
for(int i = 1;i <= n;i ++)
cin >> v[i] >> w[i];
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]);
}
cout << f[n][m];
return 0;
}
One dimensional approach :
#include<iostream>
using namespace std;
const int N = 1010;
int v[N],w[N];
int n,m;
int f[N];
int main(){
cin >> n >> m;
for(int i = 1;i <= n;i ++)
cin >> v[i] >> w[i];
for(int i = 1;i <= n;i ++)
for(int j = m;j >= v[i];j --){
f[j] = max(f[j],f[j - v[i]] + w[i]);
}
cout << f[m] << endl;
return 0;
}
First of all, I want to state , commonly DP The optimization of is to make equivalent deformation of the code , For example, the two dimensions above become one dimension , It is completely equivalent in code , Just the order of the cycle is different , Why? ?
In fact, the reason is not very difficult , First of all, let's look at this formula :f[i][j] = max(f[i][j],f[i-1][j - v[i]] + w[i]); We can see very clearly f[i-1][j - v[i]] This variable is The first i - 1 Layer of , and f[i][j] It's No i Layer of , The so-called layer here is the first for The number of cycles in . It seems that the relationship between this and reverse order is not very big , good , Then come again , Let's first assume that the cycle is from small to large , In that case ,j Is increasing ,j - v[i] It's also incremental , j - v[i] Less than or equal to j , And because of j From small to big , So in the second for in ,j - v[i] It may have appeared j 了 ( In fact, this situation is bound to happen , An example will be given later ). Actually, it's good, such as , There are two numbers a,b( hypothesis b = a - 3),a from 3 Start to grow b from 0 Start to grow ,
a: 3 4 5 6 7 8 9 10....
b: 0 1 2 3 4 5 6 7....
Found it. , As the number increases ,b The number of will be a The number that has appeared before ( ad locum ,a It's just like j , b It's just like j - v[i],3 It's like v[i], Namely b It will be in this layer a The number that has appeared ).
Well, in this case , j - v[i] Namely The first i On the floor , Then it is contradictory to the formula .
Maybe you will think like this , Then why doesn't the above situation happen in reverse order ? Here it is , When we reverse the order ,j It's from big to small ,j - v[i] From big to small ,j - v[i] Less than or equal to j, and j yes Decreasing , therefore j - v[i] Will be strictly smaller than before j 了 . Let's take the same a ,b(b = a - 3) For example
a: 10 9 8 7 6 5....
b: 7 6 5 4 3 2....
Found it. , hinder b Is strictly less than a The history of . in other words j - v[i] It's on the upper floor . Certificate completion !
Because the author is still on the way , So if there are deficiencies , Please also correct in the comment area , thank you !
I hope my explanation above is helpful to you , thank you !
边栏推荐
- 2022.02.13 - NC001. Reverse linked list
- From monomer structure to microservice architecture, introduction to microservices
- China vanadium battery Market Research and future prospects report (2022 Edition)
- Online yaml to CSV tool
- C language custom type: struct
- pcd转ply后在meshlab无法打开,提示 Error details: Unespected eof
- Summary of phased use of sonic one-stop open source distributed cluster cloud real machine test platform
- 【MySQL】数据库的存储过程与存储函数通关教程(完整版)
- [luatos-air551g] 6.2 repair: restart caused by line drawing
- Image fusion -- challenges, opportunities and Countermeasures
猜你喜欢
【云原生】手把手教你搭建ferry开源工单系统
Leetcode question brushing (5.28) hash table
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
Synchronized solves problems caused by sharing
Beijing invitation media
【MySQL】鎖
vulnhub hackme: 1
Asia Pacific Financial Media | female pattern ladyvision: forced the hotel to upgrade security. The drunk woman died in the guest room, and the hotel was sentenced not to pay compensation | APEC secur
tree树的精准查询
【MySQL】日志
随机推荐
Hcip day 16
指针和数组笔试题解析
【刷题】牛客网面试必刷TOP101
C语言自定义类型:结构体
ESP series pin description diagram summary
[MySQL] log
Bottom up - physical layer
Let the bullets fly for a while
JVM 快速入门
China polyether amine Market Forecast and investment strategy report (2022 Edition)
Upgrade tidb operator
PLT in Matplotlib tight_ layout()
【MySQL】鎖
[research materials] 2021 live broadcast annual data report of e-commerce - Download attached
[brush questions] top101 must be brushed in the interview of niuke.com
Remote storage access authorization
[research materials] 2022 enterprise wechat Ecosystem Research Report - Download attached
延迟初始化和密封类
使用 BR 备份 TiDB 集群数据到兼容 S3 的存储
指针进阶---指针数组,数组指针