大疆2019.8.6 软件笔试第三题技术分享 应该怎么吃
输入包含都租测试数据，每组数组：
第一行：买零食的开销V（V<1000）和所有零食种类数目N（N<200）
第二行：第i个正整数表示第i种零食的价格c_i（c_i<1000）
第三行：特别喜欢的零食的种类数M（2<=M<=N）
第四行：按照对M种零食的喜爱程度从高到低排序，第i种零食的喜爱程度会大于第i+1，保证不会形成环
对于每组测试数据：
输出一个整数ans，表示在满足小W的特殊爱好的情况下，并且花光所有开销，有多少可能方案；
此题涉及背包问题的求方案总数问题，使用贪心算法，不能AC，最后思考出的含条件的动态规划，使用自测数据已经通过，大致
方法是：
1.按照零食的喜爱程度重新排序，如零食价格为1 2 5 8，喜爱列表为2 3，则排序后的价格表为2 5 1 8，最后根据更新
后的价格列表进行下一步操作
2.动态规划状态转移的时候将零食依赖程度的隐含条件（价格列表前面的数量大于列表靠后的数量）附在状态转移中
//*******************大疆第三题*************************
#include<iostream>
#include<vector>
#include<unordered_map>
using namespace std;
int w[1001];
vector<int> v(1001);
int v1[1001] = {0};
struct F
{
int value;
int num;
}f[1001];
int main()
{
int m, n;
int dep_num;
while (cin >> m >> n)
{
for (int i = 1; i <= n; i++)
cin >> v[i];
cin >> dep_num;
vector<int> dep(dep_num+1);
vector<int> dep_list(dep_num + 1);
for (int i = 1; i <= dep_num; i++)
cin >> dep[i];
for (int i = 1; i < dep.size(); i++)
dep_list[i] = v[dep[i]];
f[0].value = 1;
for (int i = 1; i < 1000; i++)
{
f[i].value = 0;
f[i].num = 0;
}
int flag = 1;
for (int i = 1; i <= dep.size() - 1; i++)
{
v1[flag++] = v[dep[i]];
}
for (int i = 1; i <= dep.size() - 1; i++)
{
int tmp = dep_list[i];
vector<int>::iterator it = find(v.begin(), v.begin() + n, tmp);
if (it != v.end())
{
v.erase(it);
}
}
for (int i = flag; i <= n; i++)
{
v1[i] = v[i-flag+1];
}
f[0].value = 1;
for (int i = 1; i <= n; i++)
{
for (int j = m; j >= v1[i]; j--)
{
for (int k = 1; k <=j / v1[i]; k++)
{
if (i == 1 && f[j - k*v1[i]].value == 1)
{
f[j].value += f[j - k*v1[i]].value;
f[j].num = k;
}
else if (i>1&&i<dep.size()&&f[j-k*v1[i]].value>=1)
{
if (k >= f[j - k*v1[i]].num)
continue;
else
{
f[j].value += f[j - k*v1[i]].value;
f[j].num = k;
}
}
else
{
f[j].value += f[j - k*v1[i]].value;
}
}
}
}
cout << f[m].value << endl;
}
system("pause");
return 0;
} 
查看11道真题和解析
