Time Limit: 1 second
Memory Limit: 128 MB
【问题描述】
有两种类型的物品：普通物品和魔法物品。每种普通物品有一个价值P，但每种魔法物品有两种价值：鉴定前的价值P1和鉴定后的价值P2(保证P2>P1)。
为了鉴定一个魔法物品，你需要购买一个鉴定卷轴。鉴定完一件魔法物品以后，鉴定卷轴便会消失。每个鉴定将会消耗Pi元钱，如
果没有足够的钱，你将无法购买任何鉴定卷轴。
现在，你正在一个集市中，同时拥有很多物品。你知道每件物品的价值并且想要出售全部物品。那么，你最多能够获得多少钱呢?
你可以假定：
? 开始的时候你没有钱。
? 所有的魔法物品都还没有被鉴定。
? 只要你有足够的钱，你可以购买任意多的鉴定卷轴。
【数据规模】
0< Pi<= 5000
0 < P <= 10000
0 < P1 < P2 <= 10000
对于30%的数据 N <= 50，对于100%的数据 N <= 1000
【输入格式】
第一行有两个整数N和Pi，表示你拥有的物品数和一个鉴定卷轴价格。接下来N行，每行给出一件物品的价格。
对于每件普通物品，那一行仅有一个整数P。
对于每件魔法物品，那一行将会有两个整数P1和P2。
【输出格式】
一个整数表示你最多能够获得多少钱。
Sample Input
2 10 10 20 100
Sample Output
100
【题解】
我们先假定:值得买的魔法物品都买了（即a[2]-a[1] > pi的卷轴)，然后它们的价值是a[2]-pi;
只要能买一个鉴定轴，就所有的值得买的魔法物品都可以买了。如果卖掉了所有的普通物品和那些不值得买的魔法物品（当做普通物品卖）所凑的钱还不够买一个鉴定轴。必然要把一些已经鉴定过的魔法卷轴改为不鉴定直接卖掉以此来凑钱买一个鉴定轴。这会损失一些钱。每个值得买的魔法物品变成普通物品会损失a[2]-pi-a[1]点价值。要让损失的价值最少。就要从n个值得买的魔法物品中选出若干个物品。这些物品都有一个重量和价值。重量是它能凑的钱的数(也即a[1],也即普通物品价格),然后价值是它损失的价值。我们要让损失的价值最少。然后这个问题的容量就是所需要凑的钱的数目，也即pi减去那些不值得买的魔法物品和普通物品的价格之和。设其为m;
问题就变成一个容量为m的背包。n个物品。求能使得背包装满的最小价值。
f数组中的下标代表凑的钱的数目，最后我们要获取f[m]；然后这是一个0/1背包。要逆序更新。还有一个问题。可能所有的物品不能恰好凑到m，可能会超过m。这样我们就要记录超过了多少。最后要加上去。因为我们只要买一个卷轴就好了。剩下的钱不算是损失的。因为也是通过把魔法物品当做普通物品卖来的。
最后用之前累加的普通物品和魔法物品的和减去f[t]再加上rest[m]即可,(t在够买一个卷轴时为m),rest为这种凑的方案剩下的钱。如果把所有的魔法物品当做普通物品卖掉都不够买一个卷轴，则t!=m。
【代码】
#include <cstdio>
#include <iostream>
#include <string>
using namespace std;
int n,pi,a[1001][3],num = 0,w[1001],c[1001],f[5001],rest[5001];
int main()
{
//freopen("F:\rush.txt","r",stdin);
scanf("%d%d",&n,&pi);
for (int i = 1;i <= n;i++)
{
char t = 1;
a[i][0] = 0;
while (t != '
') //如果没有读完就继续读
{
a[i][0]++; //a[i][0]用来记录第i个物品有几个价格
scanf("%d",&a[i][a[i][0]]);
t = getchar();
}
}
int su = 0,su2 = 0; //su是把所有值得当魔法物品卖的和普通物品的价格的累加的和。
//su2则只是把普通物品的价格的累加起来。 （这里的普通物品包括不值得当魔法物品卖的物品)
for (int i = 1;i <= n;i++) //根据n个物品的信息累加
if (a[i][0] == 1)
su+=a[i][1],su2+=a[i][1];
else
{
if ((a[i][2] - a[i][1]) <= pi)
su+=a[i][1],su2+=a[i][1];
else
{
num++; //把值得当魔法物品卖的物品的信息存储下来
int temp = a[i][2]-pi;
su+=temp;
c[num] = temp-a[i][1]; //所需要损失的价值
w[num] = a[i][1]; //选num物品凑的钱数
}
}
if (su2 >= pi) //如果普通物品的累加和够买一个鉴定卷。则直接输出答案。
{
printf("%d",su); //su已经剪掉了买卷轴的钱
}
else
{
int m = pi-su2; //不够买一个卷轴 就获取要凑的钱的数目
for (int i = 0;i <= m;i++)
f[i] = 2100000000/3;
f[0] = 0; //这种是要恰好到达的不能全都置为0
for (int i = 1;i <= num;i++)
for (int j = m;j >=0;j--)
if (f[j] != (2100000000/3)) //如果能够恰好凑到j
{
int ju = (j+w[i]); //尝试选用这个物品凑钱
int re = -1; //这个re用来记录用这个物品凑钱会超过m多少钱
if (ju >= m) //如果大于等于m则记录超过m多少钱
{
ju = m;
re = ju-m;
}
if (f[ju] > f[j] + c[i]) //如果能更新解
{
f[ju] = f[j] + c[i]; //则更新解
if (re !=-1) //且记录其超过m多少钱(如果超过)
{
rest[ju] = re;
}
}
}
int tt = m;
while (f[tt] == 2100000000/3) //这是把所有值得当魔法物品的物品当做普通物品来卖都凑不够钱的情况。
//这样所有的魔法物品都会亏损。
tt--;
printf("%d",su-f[tt]+rest[m]); //减掉亏损的钱然后加上超过m的钱。
}
return 0;
}