社区讨论
这道题没有人用递归做吗?
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 条回复,欢迎继续交流。
正在加载回复...