社区讨论

这道题没有人用递归做吗?

P1049[NOIP 2001 普及组] 装箱问题参与者 8已保存回复 14

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
14 条
当前快照
1 份
快照标识符
@lo17razt
此快照首次捕获于
2023/10/22 16:35
2 年前
此快照最后确认于
2023/11/02 16:25
2 年前
查看原帖
这道题没有人用递归做吗?本蒟蒻刚开始学,如果能稳定写出下面这种水平的代码,离CSP-J三等奖还有多远?
CPP
//P1049 [NOIP2001 普及组] 装箱问题
import java.util.*;
public class Main
{
    public static int volumne,min;
    public static int[] items;
    public static void main(String args[]) 
    {
        Scanner in = new Scanner(System.in);
        volumne = Integer.parseInt(in.nextLine());
        min=volumne;
        int n =Integer.parseInt(in.nextLine());
        items = new int [n];
        for(int i1=0;i1<items.length;i1++)
            items[i1]=Integer.parseInt(in.nextLine());
        for(int i1=1;i1<=items.length;i1++)//这里设置为i1<=15可以过,但是直接归到最大物品数,最后一个测试过不了
        {
            int [] list= new int[i1]; //挑选物品方案。list存挑中物品的索引号
            boxing(-1,list,i1);
            if(min==0) 
            {
                break;
            }
        }
        System.out.println(min);
    }
    
    public static void boxing(int l, int [] list,int maxItems)
    {
        if(check(l,list)) //往下递归前排除已经装爆的方案
        {
            l++;
            if(l<maxItems) 
            {
                if(l>0)
                    list[l]=list[l-1]+1; //不能重复挑选物品,后选的物品,物品索引号至少+1          
                while (list[l]<items.length)
                {
                    boxing(l,list,maxItems);
                    list[l]++;   //物品索引号增加,一个一个物品试      
                }
            }
            else //到达本方案的最大选择物品数
            {
               int v=volumne;
               for(int i1=0;i1<list.length;i1++)
               {
                   if(v-items[list[i1]]>=0)
                       v=v-items[list[i1]];
               }
               if(v<min)
                   min=v;
            }
        }
    }
    
    public static boolean check(int l, int [] list) //排除已经装爆的方案
    {
        int v=volumne;
        for(int i1=0;i1<=l;i1++)
        {
           if(v-items[list[i1]]>=0)
               v=v-items[list[i1]];
           else
               return false;
        }
        return true;
    }
}

回复

14 条回复,欢迎继续交流。

正在加载回复...