12
11
2015
0

【noip八校联考】【动态规划】物品选取

1.物品选取 (pack.pas/c/c++)
【问题描述】 小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的背包能装的最大价值。
【样例输入输出1】
pack.in
1 0 1 1 1
pack.out
0
【样例输入输出2】
pack.in
4 10 2 1 2 1 1 1 2 3 5 2 2 200 2 3
pack.out
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;

noip前看了背包九讲后做的模拟考题,上星期重做补充了第一种情况的代码,1A~

重点是,不觉得代码写得蛮漂亮吗~?

#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<iostream>
#define inf 1000000000
#define for0(i,n) for(int i=0;i<=n;i++)
#define for1(i,n) for(int i=1;i<=n;i++)
#define mod 1000000007
using namespace std;
inline int read()
{
	int x=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9') {if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9') {x=10*x+ch-'0';ch=getchar();}
	return x*f;
}
const int M=2000+10,N=100+10;
int f[M],w[N],C[N],m[N],x[N];
int n,V,a,b,c,ans;
int cal(int a,int b,int x){return a*x*x-b*x;}
void Onepack(int c,int w)//体积 价值
{
		for(int v=V;v>=c;v--)
		f[v]=max(f[v],f[v-c]+w);
	return;
}
void Compack(int c,int w)
{
		for(int v=c;v<=V;v++)
		f[v]=max(f[v],f[v-c]+w);
	return;
}
void Mulpack(int c,int w,int m)
{
	if(c*m>=V) {Compack(c,w);return;}
	for(int k=1;k<m;k<<=1)
	{
		Onepack(k*c,k*w);
		m-=k;
	}
	Onepack(m*c,m*w);
	return ;
}
void Funpack(int a,int b)
{
	for1(i,V)
	{
		int cc,ww;
		cc=i;
		ww=cal(a,b,i);
		Onepack(cc,ww);
	}
	return;
}
int main()
{
	freopen("pack.in","r",stdin);
	freopen("pack.out","w",stdout);
	 n=read();V=read();ans=0;
	 memset(f,0,sizeof(f));
	 for1(i,n)
	 {
	 	x[i]=read();
	 	w[i]=read();
	 	C[i]=read();
	 	if(x[i]==2)
	 	m[i]=read();
	 }
	 for(int i=1;i<=n;i++)
	 {
	 	if(x[i]==2)
	 		Mulpack(C[i],w[i],m[i]);
	 	else if(x[i]==3)
	 		Compack(C[i],w[i]);
		else
			Funpack(w[i],C[i]);
	 }
	printf("%d\n",f[V]);
	return 0;
}

 

Category: 动态规划 | Tags: | Read Count: 214

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com