当前位置：网站首页>动态规划——从0-1背包问题到leetcode正则匹配
动态规划——从0-1背包问题到leetcode正则匹配
2022-08-10 05:39:00 【Scc_hy】
一、背包问题解析
- 下列是我们熟悉的背包问题的描述：
- 有n个物体，每个物体有一定的体积( v i v_i vi)，和一定的价值( p i p_i pi)。我们想挑选一些物品放入 容量为V的背包里，希望放进去的物体价值最大。
显然其中标红的部分是核心，即在一个限制条件下，将价值最大化。就和机器学习的损失函数一样，将函数最优化。
对于损失函数，我们可以基于问题是分类还是回归，来自己选定；对于我们的背包问题的价值最大化，没有一个固定式进行优化，所以很重要的一件事是我们需要找到一个结构和它的一个模式亦或是数学表达式（状态转移方程）
1.1 寻找状态转移方程
一般我们可以通过枚举观察来找出。
比如有两个数组：
进行尝试，我们知道我们需要进行不断尝试（至少两轮循环）
从上图的观察，我们选用一个二维数组作为存储结构，第一维索引我们存储的信息是放入物体的个数，第二维索引我们存放物体的体积(整数连续)，数组内存放的信息是，在存放i个物体下，体积达到j的时候最大的价值。
基于这样的结构，我们的状态转移方程存在两个种迭代方式：
加入一个物体，逐步变量连续的体积
- 体积小于加入物体的体积：当前位置的价值(
f[i][j])等于未加入该物体的时候的价值(f[i-1][j]) (即f[i][j] = f[i-1][j]) - 体积大于加入物体的体积：当前位置的价值(
f[i][j]) 有两部分比较后更新 (即f[i][j] = max(f[i-1][j], f[i-1][j-v[i]] + p[i])
a. 未加入该物体的时候的价值(f[i-1][j]
b. 加入该物体的时候的价值(f[i-1][j - v[i]] + p[i]) 将体积返回到放入物体之前j-v[i]然后加上该物体的价格p[i]
二、背包问题解
2.1 简单解
基于上述的分析，我们很容易写出解决方案(时间复杂度T(nV)，空间复杂度O(nV))
cpp
#include <iostream>
using namespace std;
int main(){
int v[4]={
10, 8, 30, 16};
int p[4]={
99, 18, 20, 56};
int V=40;
int f[5][41];
for(int i=0; i<5; i++) for(int j=0;j<41;j++) f[i][j]=0;
for(int i=1; i<5; i++){
for(int j=1; j<=V; j++){
cout << "BF: f[" << i << "][" << j << "]=" << f[i][j];
if(i==0){
f[0][j]=0;
}else if(j < v[i-1]){
f[i][j]=f[i-1][j];
}else{
f[i][j]=max(f[i-1][j], f[i-1][j-v[i-1]]+p[i-1]);
}
cout << " | AFT: f[" << i << "][" << j << "]=" << f[i][j] << endl;;
}
}
cout<< f[4][40] << endl;
return 0;
}
python
def pkg_solve(V: int, v_list: list, p_list: list):
obj_cnt = len(v_list)
p_arr=[
[0] * (V+1) for _ in range(obj_cnt+1)
]
print(obj_cnt, len(p_arr), len(p_arr[0]))
for i in range(1, obj_cnt+1):
print(i)
for j in range(1, V+1):
if(j < v_list[i-1]): p_arr[i][j] = p_arr[i-1][j]; continue;
print(f'BF: p_arr[{
i}][{
j}]={
p_arr[i][j]}', end=" ")
p_arr[i][j]=max(
p_arr[i-1][j],
p_arr[i-1][j - v_list[i-1]] + p_list[i-1]
);
print(f'| AFT: p_arr[{
i}][{
j}]={
p_arr[i][j]}')
return p_arr[obj_cnt][V]
v_list=[10, 8, 30, 16]
p_list=[99, 18, 20, 56]
V=40;
pkg_solve(V, v_list, p_list)
1.2 优化解
从结果上我们可以看出，序列仅仅在后面部分进行了更新， 所以我们可以将空间复杂度降低为O(V)
cpp
int main(){
int v[4]={
10, 8, 30, 16};
int p[4]={
99, 18, 20, 56};
int V=40;
int f[41];
for(int i=0; i<41; i++) f[i]=0;
for(int i=0; i<5; i++){
for(int j=V; j>=v[i-1]; j--){
f[j]=max(f[j], f[j-v[i-1]]+p[i-1]);
}
}
cout<< f[40] << endl;
return 0;
}
python
def update_pkg_solve(V: int, v_list: list, p_list: list):
obj_cnt = len(v_list)
p_arr = [0] * (V+1)
for i in range(1, obj_cnt+1):
for j in range(V, v_list[i-1]+1, -1):
p_arr[j]=max(
p_arr[j],
p_arr[j - v_list[i-1]] + p_list[i-1]
);
print(p_arr)
return p_arr[V]
v_list=[10, 8, 30, 16]
p_list=[99, 18, 20, 56]
V=40;
update_pkg_solve(V, v_list, p_list)
1.3 优化&泛化解——分段函数
之前我们的优化都是基于整数情况，当是浮点数据的时候，数组就不是那么好做了。
我们可以直接优化为一个分段更新的分段函数， 一个记录分段的时候的体积，一个记录分段时候的价值。
这样就按上面的思路就可以写出我们最终的优化解。
cpp
#include <iostream>
using namespace std;
int main(){
float v[4]={
10.24, 8.1, 30.6, 16.8};
float p[4]={
99, 18, 20, 56};
float V=40.8;
int v_len = sizeof(v)/sizeof(float);
int V_ceil = V / 1;
V_ceil+=1;
float break_point[42] = {
0};
float weight_point[42] = {
0};
int break_cnt = 1;
int v_tmp=0;
for(int i=1; i < v_len+1; i++){
cout << "====================================" << endl;
cout << i << " ";
v_tmp = v[i-1] / 1;
v_tmp++;
cout << v[i-1] << " " << v_tmp << endl;
for(int j=V_ceil; j >= v_tmp; j--){
if(weight_point[break_cnt-1] + v[i-1] > V) break;
if(
(break_point[break_cnt-1] + p[i-1] > break_point[break_cnt-1]) &&
(weight_point[break_cnt-1] + v[i-1] > weight_point[break_cnt-1])
){
break_point[break_cnt] = break_point[break_cnt-1] + p[i-1];
weight_point[break_cnt] = weight_point[break_cnt-1] + v[i-1];
break_cnt+=1;
break;
}
}
}
cout << break_cnt << endl;
for (int i=0; i< break_cnt; i++) cout << break_point[i] << " ";
cout << endl;
for (int i=0; i< break_cnt; i++) cout << weight_point[i] << " ";
cout << endl;
cout << "res=" << break_point[break_cnt-1];
return 0;
}
python
def float_pkg_solve(V: float, v_list: list, p_list: list):
obj_cnt = len(v_list)
break_point = [0]
weight_point = [0]
break_cnt = 1
for i in range(1, obj_cnt+1):
for j in range(int(V) + 1, int(v_list[i-1])+1, -1):
if weight_point[break_cnt-1] + v_list[i-1] > V:
break
if (break_point[break_cnt-1] + p_list[i-1] > break_point[break_cnt-1])\
and (weight_point[break_cnt-1] + v_list[i-1] > weight_point[break_cnt-1]):
break_point.append(
break_point[break_cnt-1] + p_list[i-1]
)
weight_point.append(
weight_point[break_cnt-1] + v_list[i-1]
)
break_cnt += 1
break
print(break_point)
print(weight_point)
return break_point[-1]
v_list = [10.24, 8.1, 30.6, 16.8]
# v_list=[10, 8, 30, 16]
p_list=[99, 18, 20, 56]
# p_list=[99, 18, 20, 506]
V = 40.8
float_pkg_solve(V, v_list, p_list)
三、正则匹配问题
https://leetcode-cn.com/problems/regular-expression-matching/
其实就只有用判断两个情况，后面带*不带*。对于带*分成两种， 一种是.*一种是x*
cpp
#include <iostream>
#include <string>
using namespace std;
class Solution {
public:
bool isMatch(string s, string p) {
return __isMatch(s.c_str(), p.c_str());
}
private:
bool __isMatch(const char* s, const char* p) {
if(*p == 0) return *s == 0;
bool first_match = *s && (*s == *p || *p == '.');
// .* x*
if(*(p+1) == '*'){
return isMatch(s, p+2) || (first_match && isMatch(++s, p));
}
else{
return first_match && isMatch(++s, ++p);
}
}
};
int main(){
string str_ = "ab";
string pattern = ".*";
Solution sl=Solution();
bool out;
cout << "=====================" << endl;
out = sl.isMatch(str_, pattern);
cout << "s=" << str_ << " pattern=" << pattern << " | result=" << out << endl;
cout << "=====================" << endl;
str_ = "aaa"; pattern = "a*";
out = sl.isMatch(str_, pattern);
cout << "s=" << str_ << " pattern=" << pattern << " | result=" << out << endl;
cout << "=====================" << endl;
str_ = "aaa"; pattern = "a*c*";
out = sl.isMatch(str_, pattern);
cout << "s=" << str_ << " pattern=" << pattern << " | result=" << out << endl;
cout << "=====================" << endl;
str_ = "ab"; pattern = ".*c";
out = sl.isMatch(str_, pattern);
cout << "s=" << str_ << " pattern=" << pattern << " | result=" << out << endl;
cout << "=====================" << endl;
str_ = "aab"; pattern = "c*a*b";
out = sl.isMatch(str_, pattern);
cout << "s=" << str_ << " pattern=" << pattern << " | result=" << out << endl;
cout << "=====================" << endl;
str_ = "mississippi"; pattern = "mis*is*p*.";
out = sl.isMatch(str_, pattern);
cout << "s=" << str_ << " pattern=" << pattern << " | result=" << out << endl;
cout << "=====================" << endl;
str_ = "aaa"; pattern = "aaaa";
out = sl.isMatch(str_, pattern);
cout << "s=" << str_ << " pattern=" << pattern << " | result=" << out << endl;
cout << "=====================" << endl;
str_ = "aaa"; pattern = "ab*a*c*a";
out = sl.isMatch(str_, pattern);
cout << "s=" << str_ << " pattern=" << pattern << " | result=" << out << endl;
cout << "=====================" << endl;
str_ = "ab"; pattern = ".*c*";
out = sl.isMatch(str_, pattern);
cout << "s=" << str_ << " pattern=" << pattern << " | result=" << out << endl;
return 0;
}
python
def isMatch(s, p):
if(p == ''):
return s == '';
fst = False
if s != '':
fst = s[0] and ((s[0] == p[0]) or (p[0] == '.'))
print(f's={
s} p={
p} fst={
fst}')
if(len(p) >= 2 and p[1] == '*'):
if len(s):
return isMatch(s, p[2:]) or (fst and isMatch(s[1:], p))
else:
return isMatch(s, p[2:]) or (fst and isMatch("", p))
return fst and isMatch(s[1:], p[1:])
if __name__ == '__main__':
str_ = "ab";
pattern = ".*c*";
result = isMatch(str_, pattern)
print(f"result={
result}")
str_ = "ab";
pattern = ".*c";
result = isMatch(str_, pattern)
print(f"result={
result}")
边栏推荐
猜你喜欢
随机推荐
制作一个启动软盘并用bochs模拟器启动
Hypervisor, KVM, QEMU总结
mkfs.minix.c之minix_super_block.s_ninodes获取解析
二次元卡通渲染-着色
netlink IPC
Basic use of Unity's navigation and wayfinding system
剑指 Offer（第 2 版）7/7 14-17
视差映射：更逼真的纹理细节表现（上）：为什么要使用视差映射
Kernel Image File Format
链表、栈、队列
从交换两数据值看指针的使用(c语言实现)
新手使用 go channel 需要注意的问题
Easy to master Unity of eight prior to rendering
Unity screen coordinates to world coordinates, mouse click to get 3D position
OpenGL学习笔记（LearnOpenGL）第一部分-环境配置与基础知识
内核性能分析总结
mysql分组排序并取各分组前几个数据
浅谈游戏中3种常用阴影渲染技术（3）：阴影贴图
在TypeScript中使用parseInt()
Ingress Controller performance test（1）