思路：0/1背包问题的变形
A.每张卡牌存在取与不取(a取，则b不取，b取则a不取) 两种状态，
即F[i][j] = MAX{F[i-1][j],F[i-1][abs(j - X[i-1])] + Y[i-1] }
B.这里F[i][j]表示取到第i张卡时，存在积分差j，他们的最大团队积分，
F[i -1][j] 表示不取这张卡，积分差为j时的最大团队积分;
C. F[i -1][ abs(j -X[i-1])] + Y[i-1] 表示取这张卡，对应的积分差为 abs( j - X[i-1]) 时的最大积分，加上这张卡的积分Y[i-1],
这里取绝对值是因为：
1.使用的容器（非内置数组），其下标为无符号数 ,出现负数就会导致下标越界问题
2.无论是a取还是b取其两者的分差都是正数（总是积分多的减去积分少的）
D. 这里约定无论是A取卡牌还是B取卡牌，都保证他们拥有的分数差不超过卡牌集合里最大X分值
(因为求得是分差为0时的最大团队分，所以 当一者拥有最大数值差的时候，就应该使得另一方取得卡片以减小误差，来满足积分差为0)
例：有五张卡片，他们的x值为{1,2,3,4,5}，y值为value{ 3,2,3,5,4}
则他们的分差为0时的最大积分如图1：（-1表示这种情况不存在）
从下往上，从左往右，可以看出当抽选到这五张牌的积分差为0时，团队积分和为14。
取牌{2,5} 和{3,4}
代码如下：
main .c
PackageSolution4 testpackage;
vector<int> weight{1,2,3,4,5};//卡牌的x
vector<int> value{ 3,2,3,5,4};//卡牌的y
vector<int> result = testpackage.getMaxValue(weight, value);//获得最大团队积分使用的卡牌集合
cout <<'\n' <<"使用的卡片有：";
for (int i=0; i<result.size();i++)
{
if(result[i] ==1)
cout << weight[i] << "\t";
}
PackageSolution4.c
std::vector<int>PackageSolution4::getMaxValue(std::vector<int>&weight, std::vector<int>&value)
{
int row = weight.size() + 1; //这里加1，来存储0即一张都没有的时候
int col = getMaxWeight(weight) +1; //这里的列是卡牌的x的最大值，即积分差为0-col
vector<vector<int>> array(row, vector<int>(col));
for (auto &num : array[0])//-1表示不存在这种情况
{
num = -1;
}
array[0][0] = 0;
for (int i = 1;i < row;i++)
{
for (int j = 0;j < col;j++)
{
if (array[i - 1][std::abs(j - weight[i - 1])] != -1) //满足可选条件
array[i][j] = (array[i - 1][j] > array[i - 1][std::abs(j - weight[i - 1])] + value[i - 1]) ?
array[i - 1][j] : array[i - 1][std::abs(j - weight[i - 1])] + value[i - 1];
else
array[i][j] = array[i - 1][j];
}
}
for (int i = row-1;i >=0;i--)
{
for (int j= 0;j < col;j++)
{
std::cout << array[i][j] << '\t';
}
std:;cout << std::endl;
}
vector<int> result(row-1,0);
int i = row -1;
int j = 0;
int MaxValue = array[i][j];//这个就是团队积分最大值
while (i)
{
if (array[i][j] == array[i - 1][std::abs(j - weight[i - 1])] + value[i - 1])
{
result[i-1] = 1;//表示这张卡牌被抽取了
MaxValue -= value[i - 1];
j = std::abs(j - weight[i - 1]);
}
i--;
}
if (MaxValue)
result[0] = 1;
return result;
}
int PackageSolution4::getMaxWeight(std::vector<int>&weight)
{
int max = weight[0];
for (int i = 1; i < weight.size();i++)
{
if (max < weight[i])
max = weight[i];
}
return max;
}
运行效果如下
