2602_1.cpp

HDOJ2501-2681acm解题报告

//AC!!!动态规划  453MS 3972K  背包问题
#include <iostream>
#include<string.h>
using namespace std;
int v[1001],w[1001],m[1001][1001];//m[l][j]表示物品为l个，容量为j的时候能装的最大价值
int min(int w,int c)
{return w<c?w:c;}
int max(int w,int c)
{return w>c?w:c;}
		//每个的 价值	重量  总容量  物品数
void knapsack(int v[],int w[],int c,int n,int m[1001][1001]) //求最优值
{
	int jmax=min(w[n]-1,c);
	//递归的初始条件 从m[n][j]递归到m[1][j]
	for(int j=0;j<=jmax;j++)
		m[n][j]=0;
	for(int jj=w[n];jj<=c;jj++)
		m[n][jj]=v[n];
	//递归部分
	for(int i=n-1;i>1;i--)
	{ 
		jmax=min(w[i]-1,c);//min是为了保证考虑包能放得下的东西
		for(int j=0;j<=jmax;j++)// 由于纵坐标从0开始扫描 故上面比较的jmax要减1
			m[i][j]=m[i+1][j];	//先每一层都简单的往上复制一层，下面再比较
		for(int jj=w[i];jj<=c;jj++)
			m[i][jj]=max(m[i+1][jj],m[i+1][jj-w[i]]+v[i]);
	}
	m[1][c]=m[2][c];
	if(c>=w[1])
		m[1][c]=max(m[1][c],m[2][c-w[1]]+v[1]);
	cout<<m[1][c]<<endl;
}
int main()
{
	int n,c,t;
	while(cin>>t)
	{
		while(t--)
		{
			cin>>n>>c;
			for(int i=1;i<=n;i++)
				cin>>v[i];
			for(int j=1;j<=n;j++)
				cin>>w[j];
			knapsack(v,w,c,n,m);
		}
	}
}