首页 > 试题广场 >

小萌的包裹

[编程题]小萌的包裹

热度指数：677 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

小萌是个WOW发烧友，每天都痴迷于他的法师号。精诚所至金石为开，小萌穿越到WOW的世界中了...
初来乍到的小萌在暴风城的小巷中，遇见了一位善良的德鲁伊。德鲁伊听了小萌的故事，打算帮助他在WOW这个世界好好活下去，于是，把自己的东西都给了小萌了...
德鲁伊的东西太多了，于是小萌去拍卖行买了几个包裹，一切妥当之后，小萌开始把东西装进包裹里。
不过，因为小萌穿越时候脑袋先着地，所以脑子不好用，每次他拿起一个物品，要不装进包里，要不就直接扔掉...
而且，一个背包一旦不往里装东西，小萌就会封上口不再用...
现在，告诉你小萌每个物品的体积，背包的个数和容量，以及小萌拿物品的顺序，你要帮助小萌求出他能拿走多少东西。

输入描述:

 输入的第一行为一个整数T，代表测试数据组数。
 第一行：三个正整数 N、T、M。 分别表示物品的个数，背包的容量，背包个数。
 第二行：N个数。表示每个物品的体积。
 保证：
 1<=N,T,M<=20,0<=vi<=30

输出描述:

对于每组数据，输出一个整数，代表小萌可以拿走的最多物品个数。

示例1

输入

1
5 5 2
4 3 4 2 1

输出

说明

拿出第一个背包，装第一个物品，然后封好。
拿出第二个背包，装第三个、第五个物品，然后封好。

算法知识视频讲解

Java

大表哥5263

//败给了测试数据
import java.util.*;
public class Main{
	static int MAX=0;
    public static int  sortlist(int N,int T,int M,int A[],int k,int j,int max)
    {    
    	int maxtemp=0;
    	int unm=0;
    	int B[]=new int[j-k+1];
    	B=Arrays.copyOfRange(A,k,j+1);		
    	Arrays.sort(B);
    	for(int i=0;i<=j-k;i++){
    		unm=unm+B[i];
    		if(unm>T)
    		{maxtemp=i+max;break;}
    		if(i==(j-k))
    			maxtemp=i+1+max;
    	}   
    	   return maxtemp;
  }	
    public  static void funcTion (int N,int T,int M,int A[],int k,int n,int max)//m是开始的坐标，n是标志位，k是数组的最大值；max是每一个的共个数
    {  if(n==M-1)
       {
    	int z=Main.sortlist(N,T, M, A,k,N-1,max);//n
    	    if(z>Main.MAX)
		    {Main.MAX=z;}
	    }else{
    	for(int i=k;i<N;i++)//i表示结束的下表
    	{
    		int z=Main.sortlist(N,T, M, A,k,i,max);//n
    		Main.funcTion(N,T,M,A,i+1,n+1,z);
    		
    	}}
    }
  	public static void main(String[] args) 
	{
	    Scanner scan=new Scanner(System.in);
	    int K=scan.nextInt();
	    while((K--)>0)
	    {
	    	int N=scan.nextInt();
	    	int T=scan.nextInt();
			int M=scan.nextInt();
			int A[]=new int[N];
	    	for(int i=0;i<N;i++)
	    	{
	    		A[i]=scan.nextInt();
	    	}
	    	Main.funcTion(N,T,M,A,0,0,0);
	    	System.out.println(Main.MAX);
	    	Main.MAX=0;
	    }
		scan.close();
	 }

}

编辑于 2016-10-27 15:43:03 回复(0)