#include 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; }