物品选取
题目描述：
小X确信所有问题都有个多项式时间算法，为了证明，他决定自己去当一次旅行商，在上路之前，小X需要挑选一些在路上使用的物品，但他只有一个能装体积为(m)的背包。显然，背包问题对小X来说过于简单了，所以他希望你来帮他解决这个问题。
小X可以选择的物品有(n)样，一共分为甲乙丙三类：
1甲类物品的价值随着你分配给他的背包体积变化，它的价值与分配给它的体积满足函数关系式，(v(x) = A*x^2-Bx)，(A)，(B)是每个甲类物品的两个参数。注意每个甲类物品最多只能够用一次。
2乙类物品的价值(A)和体积(B)都是固定的，但是每个乙类物品都有个参数(C)，表示这个物品可供选择的个数。
3丙类物品的价值(A)和体积(B)也是固定的，但是每个丙类物品可供选择的个数都是无限多个。
你最终的任务是确定小X的背包最多能装有多大的价值上路。
输入格式：
第一行两个整数(n)，(m)，表示背包物品的个数和背包的体积；
接下来(n)行，每行描述一个物品的信息。第一个整数x，表示物品的种类：
若(x)为1表示甲类物品，接下来两个整数(A), (B)，为(A)类物品的两个参数；
若(x)为2表示乙类物品，接下来三个整数(A)，(B)，(C)。(A)表示物品的价值，(B)表示它的体积，(C)表示它的个数；
若(x)为3表示丙类物品，接下来两个整数(A)，(B)。(A)表示它的价值，(B)表示它的体积。
输出格式：
输出文件仅一行为一个整数，表示小X的背包能装的最大价值。
样例输入：
4 10 2 1 2 1 1 1 2 3 5 2 2 200 2 3
样例输出：
610
数据范围：
对于(50\%)的数据，只有乙和丙两类物品；
对于(70\%)的数据，(1<=n<=100), (1<=m<=500)，(0<=A,B,C<=200)；
对于(100\%)的数据，(1<=n<=100), (1<=m<=2000)，(0<=A,B,C<=200)；
时间限制：
1s
空间限制：
256M
提示：
remove!!!
题解
题目都说这是一个背包问题了，当然要顺从以下出题者的意愿了。
乙类物品和丙类物品就是简单的有限背包和无限背包了，正常打就好了。
没学过背包问题的请自行解决。
至于甲类物品，题目说每个甲类物品最多只能够用一次，那么就有点像01背包了，只不过甲类物品的重量和价值是不固定的。
所以正常背包，在里面再枚举一下甲类物品的重量就好了。
上代码：
#include<bits/stdc++.h>
using namespace std;
int n,m;
int a,b,c,x;
int dp[2009];
int ans;
int main(){
scanf("%d%d",&n,&m);
for(int j=1;j<=n;j++){
scanf("%d",&x);
if(x==1){
scanf("%d%d",&a,&b);
for(int j=m;j>=1;j--)
for(int i=1;j+i<=m;i++)
if(dp[j]>0) dp[j+i]=max(dp[j+i],dp[j]+a*i*i-b*i);//注意要先枚举背包的重量再枚举甲类物品的重量，否则就无法满足每个甲类物品最多只能够用一次的条件了
for(int i=1;i<=m;i++)
dp[i]=max(dp[i],a*i*i-b*i);
}else if(x==2){
scanf("%d%d%d",&a,&b,&c);
for(int j=1;j<=c;j++){
for(int i=m-b;i>=1;i--)
if(dp[i]>0) dp[i+b]=max(dp[i+b],dp[i]+a);
dp[b]=max(dp[b],a);
}
}else if(x==3){
scanf("%d%d",&a,&b);
dp[b]=max(dp[b],a);
for(int i=1;i+b<=m;i++)
if(dp[i]>0) dp[i+b]=max(dp[i+b],dp[i]+a);
}
}
for(int j=1;j<=m;j++)
ans=max(ans,dp[j]);
printf("%d",ans);
return 0;
}