Time Limit: 1 second
Memory Limit: 128 MB
【问题描述】
小X来到一个雄奇的金字塔挖宝，但是这是一座被诅咒的金字塔，小X必须马上逃离这里，否则小X就会被埋在金字塔里，但他不希望此行落空。现在小X面前有N+1种财宝，每种财宝都有一个价值。第一种财宝重量为0，第二种财宝重量为1，总之第I种财宝重量为I-1。现在小X希望
拿走N+M个物品，但是这M+N个物品总重量不能超过N。小X希望能获得最大的价值。你能帮帮他吗？
由于金字塔跟小X一样牛，所以每种财宝无限个。
【输入格式】
第一行两个正整数N，M 第二行N+1个整数，第I个整数代表了第I种财宝的价值
【输出格式】
一个数，表示最大利润。
【数据规模】
10%满足N,M<=10 40%满足N,M<=100 100%满足 N,M<=3000 abs(财宝价值)<=1000
Sample Input1
5 3 4 7 2 5 -3 6
Sample Output1
47
【题解】
这题有两个很烦人的地方，一个是m+n个物品的限制。一个是重量为0的物品。
我们要怎么去除掉这个问题呢。
首先考虑一下最后我们选取的物品。
因为规定了要选m+n个物品。如果不选重量为0的物品可能会出现选不够的问题。
因此必然是掺杂着重量为0和重量不为0的物品。设为x，y.
设重量为0的物品下标为0,重量不为0的物品下标为1..n;
c是物品价值数组，w是物品的重量数组。
最后的答案 == x*c[0] + y*c[0] +∑(c[i]) - y*c[0] （其中的求和为所选出的最优的y个有重量的物品的价值的和）;
但是先别急着划掉两个y*c[0]；
我们合并一下。ans == (x+y)*c[0] + ∑(c[i]) - y*c[0]；
其中x+y==n+m;
ans == (n+m)*c[0] + ∑(c[i]) - y*c[0];
其中左边绿色部分为常量，右边为需要求的量。
因为∑（c[i]）一共求和了y(未知)个c[i]，则可以再化一下。
ans == 常量 + ∑（c[i]-c[0]） i∈【1,n】
这下问题就变成求物品重量为w[i],价值为c[i]-c[0]的完全背包问题了。
右边最大则ans最大。
还有一个优化的方法。即如果c[i]-c[0]是小于0的，那么这个物品就不要了。
因为如果c[i]比c[0]还小，那么拿不用重量的物品来替代i物品肯定最优。（c[0]不用消耗重量！）
【代码】
#include <cstdio>
int n,m,temp,num = 0,f[3011],w[3011],c[3011];
void input_data()
{
scanf("%d%d",&n,&m);
scanf("%d",&temp); //读入c[0]
for (int i = 1;i <= n;i++)
{
int x;
scanf("%d",&x);
x -= temp; //输入第i个物品的价值，先减去c[0]
if (x > 0) //如果减去后还大于0则这个物品是可能在y个物品中的。
{
num++;
w[num] = i;
c[num] = x;
}
}
}
void get_ans()
{
for (int i = 1;i <= num;i++) //对c[i]-c[0] (i∈[1..n]) 进行完全背包的过程
for (int j = w[i];j <= n;j++)
if (f[j] < f[j-w[i]] + c[i])
f[j] = f[j-w[i]] + c[i];
}
void output_ans()
{
printf("%d",f[n] + (n+m)*temp); //最后输出f[n]的时候还要加上被减去的y个c[0]。以及x个c[0]；
}
int main()
{
//freopen("F:\rush.txt","r",stdin);
input_data();
get_ans();
output_ans();
return 0;
}