//解决行李打包问题的动态规划算法 int n,capacity; int volume[100],need[100]; int cache[1001][1001] //行李箱剩余空间为capicity时,将返回放入item以后物品所能得到的必要程度最大值 int pack(int capacity,int item) { if(item == n) { return 0; } int &ret =cache[capacity][item]; if (ret != -1) { return ret; } //不放当前物品到包里 ret=pack(capacity,item+1); if(capacity >=volume[item]) { ret= max(ret,pack(capacity- capacity[item],item+1)+need[item]; } return ret; } //获取放入包中的东西内容 void reconstruct(int capacity,int item, vector<string> &picked) { if(item == n) { return; } if(pack(capacity,item) == pack(capacity,item+1)) { reconstruct(capacity,item+1,picked); } else { picked.push_back(name[item]); reconstruct(capacity-volume[item],item+1,picked); } } 将上述代码转化为Python代码
时间: 2024-03-16 18:41:42 浏览: 16
以下是将该动态规划算法的C++代码转化为Python代码的结果:
```
n = 0
capacity = 0
volume = []
need = []
cache = []
# 行李箱剩余空间为capacity时,将返回放入item以后物品所能得到的必要程度最大值
def pack(capacity, item):
global n, volume, need, cache
if item == n:
return 0
ret = cache[capacity][item]
if ret != -1:
return ret
# 不放当前物品到包里
ret = pack(capacity, item+1)
if capacity >= volume[item]:
ret = max(ret, pack(capacity - volume[item], item+1) + need[item])
cache[capacity][item] = ret
return ret
# 获取放入包中的东西内容
def reconstruct(capacity, item, picked):
global n, name, volume
if item == n:
return
if pack(capacity, item) == pack(capacity, item+1):
reconstruct(capacity, item+1, picked)
else:
picked.append(name[item])
reconstruct(capacity - volume[item], item+1, picked)
```
需要注意的是,Python中没有C++中的引用类型,因此在Python代码中需要使用`global`关键字来声明全局变量。此外,Python中也没有C++中的指针类型,因此在Python代码中直接使用二维数组即可,不需要使用指针。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)