杭电-2602Bone Collector

淩亂°似流年 2022-08-09 12:48 140阅读 0赞

# Bone Collector #

**Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)**

Total Submission(s): 41338 Accepted Submission(s): 17209

Problem Description

Many years ago , in Teddy’s hometown there was a man who was called “Bone Collector”. This man like to collect varies of bones , such as dog’s , cow’s , also he went to the grave …  
The bone collector had a big bag with a volume of V ,and along his trip of collecting there are a lot of bones , obviously , different bone has different value and different volume, now given the each bone’s value along his trip , can you calculate out the maximum of the total value the bone collector can get ?  
![C154-1003-1.jpg][]

Input

The first line contain a integer T , the number of cases.  
Followed by T cases , each case three lines , the first line contain two integer N , V, (N <= 1000 , V <= 1000 )representing the number of bones and the volume of his bag. And the second line contain N integers representing the value of each bone. The third line contain N integers representing the volume of each bone.

Output

One integer per line representing the maximum of the total value (this number will be less than 2 31).

Sample Input

1
    5 10
    1 2 3 4 5
    5 4 3 2 1

Sample Output

简单dp中的0-1背包问题！

#include<cstdio>
    #include<cstring>
    #include<algorithm>
    using namespace std;
    int f[1010][1010];
    int main()
    {
    	int N,val[1010],vol[1010],i,m,n,j;
    	scanf("%d",&N);
    	while(N--)
    	{
    		scanf("%d%d",&m,&n);
    		for(i=1;i<=m;i++)
    			scanf("%d",&val[i]);
    		for(i=1;i<=m;i++)
    			scanf("%d",&vol[i]);
    		memset(f,0,sizeof(f));
    		for(i=1;i<=m;i++)
    		{
    			for(j=0;j<=n;j++)//背包容量可以为0
    			{
    				if(vol[i]<=j)
    					f[i][j]=max(f[i-1][j],f[i-1][j-vol[i]]+val[i]);
    				else
    					f[i][j]=f[i-1][j];
    			}
    		}
    		printf("%d\n",f[m][n]);
    	}
    	return 0;
     }

优化后！

#include<cstdio>
    #include<cstring>
    #include<algorithm>
    using namespace std;
    int f[1010],weight[1010],val[1010];
    int main()
    {
    	int N,i,j,m,n;
    	scanf("%d",&N);
    	while(N--)
    	{
    		scanf("%d%d",&m,&n);
    		for(i=1;i<=m;i++)
    		scanf("%d",&val[i]);
    		for(i=1;i<=m;i++)
    		scanf("%d",&weight[i]);
    		
    		memset(f,0,sizeof(f));
    		for(i=1;i<=m;i++)
    		{
    			for(j=n;j>=weight[i];j--)
    			{
    				f[j]=max(f[j],f[j-weight[i]]+val[i]);
    			}
    		}
    		printf("%d\n",f[n]);
    	}
    	return 0;
    }

[C154-1003-1.jpg]: /images/20220731/c52869f7cccc40e9a529ec9b8dccccea.png