67 lines
2.5 KiB
C++
67 lines
2.5 KiB
C++
#include <bits/stdc++.h>
|
||
|
||
using namespace std;
|
||
|
||
int n, k, sum;
|
||
int c[101]; //价钱
|
||
int num[101]; //
|
||
int m[101]; //美味价值
|
||
int f[1001], number, bi;
|
||
bool b[101]; //b数组是由来确定他是否为已处理过的必选菜。
|
||
|
||
//01背包问题，注意两个小问题就好了:
|
||
// 1.把价格和money都扩大十倍。
|
||
// 2.同一物品会出现两次，然并卵。所幸题目提示了，用种类哈希数组映射到vis上去就好了，如果是必选物品i就设置vis[i]为0。
|
||
int main() {
|
||
//输入+输出重定向
|
||
freopen("../1300.txt", "r", stdin);
|
||
|
||
//b数组是由来确定他是否为已处理过的必选菜。
|
||
memset(b, false, sizeof(b));
|
||
|
||
//有n个菜式，有k种菜是必选的，小松带来了X元钱（精确到“角”）。
|
||
double x;
|
||
scanf("%d%d%lf", &n, &k, &x);
|
||
|
||
int tot = (int) (x * 10);//为了方便处理，在这里我们把价钱全部乘10。
|
||
//表示菜桌上从入口到出口的所有菜的价格
|
||
//由于价钱是精确到角的,所以这里*10不影响该题的答案
|
||
double a;
|
||
for (int i = 1; i <= n; i++) {
|
||
scanf("%lf", &a);
|
||
c[i] = (int) (a * 10);
|
||
}
|
||
|
||
//表示菜桌上从入口到出口的所有菜的美味价值
|
||
for (int i = 1; i <= n; i++)
|
||
scanf("%d", &m[i]);
|
||
|
||
//表示菜桌上从入口到出口的所有菜的种类编号
|
||
for (int i = 1; i <= n; i++) {
|
||
scanf("%d", &number);
|
||
num[number] = i;//编号相同的菜后来的会覆盖掉前面的，这样接下来处理就简单了
|
||
} //在这个地方我们把输入的数当成下标，存放下标的位置，就很容易寻找它对应的价值和美味值..
|
||
|
||
for (int i = 1; i <= k; i++) {
|
||
scanf("%d", &bi);//读入种类
|
||
tot -= c[num[bi]]; //根据种类，换算出价格
|
||
sum += m[num[bi]]; //根据种类，换算出美味值
|
||
b[bi] = true; //注意：在这个时候b[]内是bi;
|
||
}
|
||
//tot就是上限的价格，也可以理解为就是背包的上限容量
|
||
//sum就是最终的美味值和，目前只是必选菜的美味值和
|
||
|
||
//01背包
|
||
for (int i = 1; i <= n; i++)
|
||
if (!b[i]) //如果不是必选菜，才能进行01背包处理
|
||
for (int j = tot; j >= c[num[i]]; j--) {
|
||
f[j] = max(f[j], f[j - c[num[i]]] + m[num[i]]);//01背包求解
|
||
}
|
||
|
||
//输出结果
|
||
printf("%d", f[tot] + sum);
|
||
//关闭文件
|
||
fclose(stdin);
|
||
return 0;
|
||
}
|