2019阿里暑期实习笔试题个人思路
2019阿里暑期实习笔试题个人思路
个人思路：
- 斐波那契数列求出小猪列表，注意猪的年龄大等于3的每次循环生一只猪，之前理解需要年龄大于3才可以生小猪，查错好久。
- 循环小猪列表，反转编号，进行排序，获取第k大的索引。
- 小猪类的成员包含年龄，索引，出生年份，编号，索引是为了第二问，或者第二问另开一个列表保存排序后的小猪列表，然后拿着第k大的小猪去原列表中获取下标索引。
个人思路：
- 多维背包问题。
- 因为种类的冲突，考虑把冲突的种类分开，做两次动态规划，取其最大值。
- 或者再开一个三维数组num[i][v][m]，记录dp[i][v][m]数组每种情况生鲜类的装载个数，在添加美妆种类物品时，计算每种dp[i][v][m]最大值时，减去对应的num[i][v][m]个生鲜类物品
备注：题目的用例，取1个第二种物品，5个第三种物品，可以达到36价值，感觉时用例错误
多维背包问题
背包用来装旅游物品，现在共n种(n<=50)旅游物品，每种物品都有体积vi，重量wi，数量ci，价值ti (vi,wi,ci和ti都为整数)。
限制体积最多V立方厘米(V<=1000)，重量最多W公斤(W<=500)。
请问你如何选择物品，使得带上的物品总价值最大，这个最大总价值为多少？
比如：
物品编号(i) 体积(V) 重量(M) 数量(num) 价值(price)
1 30 3 10 4
2 50 8 10 5
3 10 2 10 2
4 23 5 8 3
5 130 20 5 11
可以使用dfs加剪枝暴力求解，但是效率感人
使用动态规划求解，状态转移数组dp[i][v][m]表示选取前i种物品，体积为v，重量为m时最大价值
状态转移方程如下：
选取第一种物品时，
dp[1][v][m] = 0 v < V[1] || m < M[1]
dp[1][v][m] = min(v/V[1],m/M[1],num[1]) * price[1] v >= V[1] && m >= M[1]
选取第二种物品到最后一种物品:
dp[i][v][m] = dp[i-1][v][m] v < V[i] || m < M[i]
dp[i][v][m] = max(dp[i - 1][v][m],dp[i - 1][v - k * V[i]][m - k*M[i]] + k * price[i])) v >= V[i] && m >= M[i],k表示放入几个该第i种物品