一道JAVA游戏算法题

Question

一个游戏：你有n张防御卡Di，价值相应为wi，防御能力为di。你的对手有进攻卡Aj，进攻能力为aj。如果Di与Aj相遇，且di<aj时，防御卡就死掉。你的任务是安排一种匹配， 使得存活防御卡的剩余价值最大。给出你的算法，并说明正确性。求指教 求算法 求代码，这个题目看了不知道从何下手，是不是要想田忌赛马那样做呢？

Answer 1

我有个想法 不知对错
先把 A 按攻击力非降序排好序
在把 B 一个个取出来用2分找到 A 中那个不能杀掉B且是最大的那个
如果这个位置目前还没匹配上 B， 那么把当前 B 与 A 匹配
如果这个位置有其他的 B 牌，
那么比较这2张B牌的价值，把价值大的与A匹配
价值小的那个B牌与当前A之前的其他A中的B牌比较（能不被当前A杀死的必然不能比之前的A杀死）
把价值小的那个B牌找到一个合适的位置与A匹配

Answer 2

能不能这样对Aj中的任何一个，按下面规则匹配Dj1、如果Dj中有比Aj大的牌，则选择与Aj牌攻击力相差最小的一张牌去匹配..2、如果Dj中没有比当前Aj牌大的牌，则选择Dj中剩余的最小的一张去匹配...

Answer 3

上面错了，漏看了，DJ的牌还有个价值WI...要求的是剩余价值最大..

Answer 4

我个人的想法：无法证明是最优解，但是也找不出哪里错了...1、把Dj牌按 价值--防御的顺序 逆序排列 （价值最高的牌需要最优先保证存活）2、把Aj牌按升序排列 （这个升降序 无所谓，反正要排次）3、按顺序遍历Dj牌，对于每个牌，优先找与其防御值最近但是不大于该防御值的Aj牌匹配。如果找不到则将其与攻击最大的牌匹配（废牌要最佳利用嘛）;代码和执行结果如下....写的很烂随便看看，我也不知道怎么证明这个思路是对的或者错的...public class zzz {
//第一位表示防御值，第二位表示价值
private static int[] Dj = new int[] { 11, 23, 45, 22, 12, 55, 42, 56, 91 };
private static int[] Aj = new int[] { 11, 4, 2, 4, 5, 6, 7, 8, 4 };
private static int totalVal = 0;

public static void main(String args[]) {
//按价值-防御 逆序对原数组排序
for (int i = 0; i < Dj.length; i++){
for(int j = i+1; j<Dj.length ;j++){
int val_i = Dj[i] % 10;
int def_i = Dj[i] / 10;
int val_j = Dj[j] % 10;
int def_j = Dj[j] / 10;
if(val_i<val_j){
change(Dj,i,j);
}else if(val_i==val_j){
if(def_i<def_j){
change(Dj,i,j);
}
}
}
}
//把攻击升序排列
for (int i = 0; i < Aj.length; i++){
for(int j = i+1; j<Aj.length ;j++){
if(Aj[i]>Aj[j]){
change(Aj,i,j);
}
}
}
for (int i = 0; i < Dj.length; i++){
getFixedNum(Dj[i],Aj);
}
System.err.println("总价值："+totalVal);

} private static void change(int[] nums, int i, int j) {
int num = nums[i];
nums[i] = nums[j];
nums[j] = num;
}

private static void getFixedNum(int Dj,int[] Aj){
boolean canSuc = false;
//找到与防御值最接近的且不大于改值的攻击值
for(int i = Aj.length-1; i >=0; i--){
if(Aj[i]<=Dj/10 && Aj[i] != -1){
System.err.println("配对："+Dj+"--"+Aj[i]);
totalVal += Dj%10;
Aj[i] = -1; //已用过的攻击牌置为-1
canSuc = true;
break;
}
}
//如果无法找到，则找到最大的攻击值
if(!canSuc){
for(int i = Aj.length-1; i >=0; i--){
if( Aj[i] != -1){
System.err.println("配对："+Dj+"--"+Aj[i]);
Aj[i] = -1;
break;
}
}
}
}
}result：
配对：56--5
配对：55--4
配对：45--4
配对：23--2
配对：42--4
配对：22--11
配对：12--8
配对：91--7
配对：11--6
总价值：22