16 个解决方案
#1
用递归试一试
想出来,我给你答案
想出来,我给你答案
#2
设要截的数目分别为c5,c7,c9,c10：
1.截9M的：9+9，9+7(或9+5)
2.截10M： 10+7 ，10+5，10+0；
3.截7M的：7+5+5，7+7，7+5，7+0；
4.截5M的：5+5+5，5+5，5+0
每个都是前面的条件不满足了才往后看
1.截9M的：9+9，9+7(或9+5)
2.截10M： 10+7 ，10+5，10+0；
3.截7M的：7+5+5，7+7，7+5，7+0；
4.截5M的：5+5+5，5+5，5+0
每个都是前面的条件不满足了才往后看
#3
写错了，第1点应该是这样：
1.截9M的：9+9，9+7，9+5，9+0；
1.截9M的：9+9，9+7，9+5，9+0；
#4
int test(int c5,int c7,int c9,int c10)
{
int n=0;
n += c9/2;
if(c9%2)
{
n++;
if(c7)
c7-=1;
else if(c5)
c5-=1;
}
if(c10)
{
n += c10;
if(c7<c10 )
{
c10 -= c7;
c7 = 0;
if(c5>=c10)
{
c5-=c10;
}
else
c5=0;
}
else
c7 -= c10;
}
while(c7)
{
if(c5>=2)
{
if(c7*2>=c5)
{
c7-=c5/2;
n += c7;
c5 = 0;
}
else
{
c5-=c7*2;
n += c5/2;
c7=0;
}
}
else
{
n+= (c5+c7)/2;
c5=0;
c7=0;
}
}
if(c5)
n+= (c5+2)/3;
return n;
}
{
int n=0;
n += c9/2;
if(c9%2)
{
n++;
if(c7)
c7-=1;
else if(c5)
c5-=1;
}
if(c10)
{
n += c10;
if(c7<c10 )
{
c10 -= c7;
c7 = 0;
if(c5>=c10)
{
c5-=c10;
}
else
c5=0;
}
else
c7 -= c10;
}
while(c7)
{
if(c5>=2)
{
if(c7*2>=c5)
{
c7-=c5/2;
n += c7;
c5 = 0;
}
else
{
c5-=c7*2;
n += c5/2;
c7=0;
}
}
else
{
n+= (c5+c7)/2;
c5=0;
c7=0;
}
}
if(c5)
n+= (c5+2)/3;
return n;
}
#5
to: yjm0105(流云)
谢谢你的回答，（需要5米的钢条6条，7米的钢条8条，9米的钢条12条，10米的钢条5条）只是给的例子，可能我还需要0.5米20条或者别的什么，就是这个也不固定，能不能得到一个数学公式出来，我开始考虑是用数组穷举，先任两个加和为18取出，剩下的和小于18的再三个加，这样一直穷举下去，发现加的个数就是维数，会出现无穷维。
谢谢你的回答，（需要5米的钢条6条，7米的钢条8条，9米的钢条12条，10米的钢条5条）只是给的例子，可能我还需要0.5米20条或者别的什么，就是这个也不固定，能不能得到一个数学公式出来，我开始考虑是用数组穷举，先任两个加和为18取出，剩下的和小于18的再三个加，这样一直穷举下去，发现加的个数就是维数，会出现无穷维。
#6
这个，不会了，大汗~~~
#7
这种东西哪会有公式的，我这么考虑，把需要的钢条按长度递减排序，切的时候在原始条里挑最短的但能满足当前任务长度的条来切，不知道可不可行。
#8
贪心即可, 只要充分利用每一根钢材即可, 所以只要考虑一根钢材的情况:
设m为需要的钢条长度, n为该种长度需要的条数, x为实际从一根钢材中截取的该种钢条的条数
即求 m[1]*x[1]+m[2]*x[2]+...+m[i]*x[i] 的最大值, 当然要小于等于一根钢材的长度, 且x[i]<=n[i]
DP一下就可以了, 或者强行搜索一下也行
设m为需要的钢条长度, n为该种长度需要的条数, x为实际从一根钢材中截取的该种钢条的条数
即求 m[1]*x[1]+m[2]*x[2]+...+m[i]*x[i] 的最大值, 当然要小于等于一根钢材的长度, 且x[i]<=n[i]
DP一下就可以了, 或者强行搜索一下也行
#9
谢谢各位的回答。
我现在有个想法，首先给所需要的钢条从大到小排序，然后将1根钢条，2根钢条，3根钢条...N根钢条相加，一直加到和都大于18，小于等于18的所有可能组成一个数组。先处理等于18的，最少的个数相加等于18就取出来（例17米和1米、1米12米5米，就取17米和1米），相同个数就取最大数字在的那组（例15米2米1米、9米2米7米，就取15米2米1米），处理完等于18的在处理小于18的，越接近18先取出，相同的情况处理和18米一样。
语言表达能力不行，不知道大家看懂没有，给个意见。
我现在有个想法，首先给所需要的钢条从大到小排序，然后将1根钢条，2根钢条，3根钢条...N根钢条相加，一直加到和都大于18，小于等于18的所有可能组成一个数组。先处理等于18的，最少的个数相加等于18就取出来（例17米和1米、1米12米5米，就取17米和1米），相同个数就取最大数字在的那组（例15米2米1米、9米2米7米，就取15米2米1米），处理完等于18的在处理小于18的，越接近18先取出，相同的情况处理和18米一样。
语言表达能力不行，不知道大家看懂没有，给个意见。
#10
要把一种钢条重复取的情况考虑进去, 就是可重复的组合。和相同说明钢材利用率一样, 哪个先取都一样吧
#11
Michaelgs,请问DP是什么算法？
#12
To楼上 DP就是动态规划
#13
感觉这个像分段内存分配，呵呵
#14
It's called 'Bin Packing Problem'.
Check http://www.cs.gsu.edu/~cscskp/Algorithms/NP/node11.html
Check http://www.cs.gsu.edu/~cscskp/Algorithms/NP/node11.html
#15
完成了功能，现在效率差，钢条个数40个以上超级慢！！！
#16
呵呵
兄弟,这是背包问题
你可以查一些文献,或者是上网搜搜都可以.
我知道它肯定是背包问题
但是我从来没有学过.
我们老师和我说过.
它说的问题是这样的
有1米的直线,和10,20,30厘米的小线段
怎么放能放最多条数的直线.
兄弟,这是背包问题
你可以查一些文献,或者是上网搜搜都可以.
我知道它肯定是背包问题
但是我从来没有学过.
我们老师和我说过.
它说的问题是这样的
有1米的直线,和10,20,30厘米的小线段
怎么放能放最多条数的直线.
#1
用递归试一试
想出来,我给你答案
想出来,我给你答案
#2
设要截的数目分别为c5,c7,c9,c10：
1.截9M的：9+9，9+7(或9+5)
2.截10M： 10+7 ，10+5，10+0；
3.截7M的：7+5+5，7+7，7+5，7+0；
4.截5M的：5+5+5，5+5，5+0
每个都是前面的条件不满足了才往后看
1.截9M的：9+9，9+7(或9+5)
2.截10M： 10+7 ，10+5，10+0；
3.截7M的：7+5+5，7+7，7+5，7+0；
4.截5M的：5+5+5，5+5，5+0
每个都是前面的条件不满足了才往后看
#3
写错了，第1点应该是这样：
1.截9M的：9+9，9+7，9+5，9+0；
1.截9M的：9+9，9+7，9+5，9+0；
#4
int test(int c5,int c7,int c9,int c10)
{
int n=0;
n += c9/2;
if(c9%2)
{
n++;
if(c7)
c7-=1;
else if(c5)
c5-=1;
}
if(c10)
{
n += c10;
if(c7<c10 )
{
c10 -= c7;
c7 = 0;
if(c5>=c10)
{
c5-=c10;
}
else
c5=0;
}
else
c7 -= c10;
}
while(c7)
{
if(c5>=2)
{
if(c7*2>=c5)
{
c7-=c5/2;
n += c7;
c5 = 0;
}
else
{
c5-=c7*2;
n += c5/2;
c7=0;
}
}
else
{
n+= (c5+c7)/2;
c5=0;
c7=0;
}
}
if(c5)
n+= (c5+2)/3;
return n;
}
{
int n=0;
n += c9/2;
if(c9%2)
{
n++;
if(c7)
c7-=1;
else if(c5)
c5-=1;
}
if(c10)
{
n += c10;
if(c7<c10 )
{
c10 -= c7;
c7 = 0;
if(c5>=c10)
{
c5-=c10;
}
else
c5=0;
}
else
c7 -= c10;
}
while(c7)
{
if(c5>=2)
{
if(c7*2>=c5)
{
c7-=c5/2;
n += c7;
c5 = 0;
}
else
{
c5-=c7*2;
n += c5/2;
c7=0;
}
}
else
{
n+= (c5+c7)/2;
c5=0;
c7=0;
}
}
if(c5)
n+= (c5+2)/3;
return n;
}
#5
to: yjm0105(流云)
谢谢你的回答，（需要5米的钢条6条，7米的钢条8条，9米的钢条12条，10米的钢条5条）只是给的例子，可能我还需要0.5米20条或者别的什么，就是这个也不固定，能不能得到一个数学公式出来，我开始考虑是用数组穷举，先任两个加和为18取出，剩下的和小于18的再三个加，这样一直穷举下去，发现加的个数就是维数，会出现无穷维。
谢谢你的回答，（需要5米的钢条6条，7米的钢条8条，9米的钢条12条，10米的钢条5条）只是给的例子，可能我还需要0.5米20条或者别的什么，就是这个也不固定，能不能得到一个数学公式出来，我开始考虑是用数组穷举，先任两个加和为18取出，剩下的和小于18的再三个加，这样一直穷举下去，发现加的个数就是维数，会出现无穷维。
#6
这个，不会了，大汗~~~
#7
这种东西哪会有公式的，我这么考虑，把需要的钢条按长度递减排序，切的时候在原始条里挑最短的但能满足当前任务长度的条来切，不知道可不可行。
#8
贪心即可, 只要充分利用每一根钢材即可, 所以只要考虑一根钢材的情况:
设m为需要的钢条长度, n为该种长度需要的条数, x为实际从一根钢材中截取的该种钢条的条数
即求 m[1]*x[1]+m[2]*x[2]+...+m[i]*x[i] 的最大值, 当然要小于等于一根钢材的长度, 且x[i]<=n[i]
DP一下就可以了, 或者强行搜索一下也行
设m为需要的钢条长度, n为该种长度需要的条数, x为实际从一根钢材中截取的该种钢条的条数
即求 m[1]*x[1]+m[2]*x[2]+...+m[i]*x[i] 的最大值, 当然要小于等于一根钢材的长度, 且x[i]<=n[i]
DP一下就可以了, 或者强行搜索一下也行
#9
谢谢各位的回答。
我现在有个想法，首先给所需要的钢条从大到小排序，然后将1根钢条，2根钢条，3根钢条...N根钢条相加，一直加到和都大于18，小于等于18的所有可能组成一个数组。先处理等于18的，最少的个数相加等于18就取出来（例17米和1米、1米12米5米，就取17米和1米），相同个数就取最大数字在的那组（例15米2米1米、9米2米7米，就取15米2米1米），处理完等于18的在处理小于18的，越接近18先取出，相同的情况处理和18米一样。
语言表达能力不行，不知道大家看懂没有，给个意见。
我现在有个想法，首先给所需要的钢条从大到小排序，然后将1根钢条，2根钢条，3根钢条...N根钢条相加，一直加到和都大于18，小于等于18的所有可能组成一个数组。先处理等于18的，最少的个数相加等于18就取出来（例17米和1米、1米12米5米，就取17米和1米），相同个数就取最大数字在的那组（例15米2米1米、9米2米7米，就取15米2米1米），处理完等于18的在处理小于18的，越接近18先取出，相同的情况处理和18米一样。
语言表达能力不行，不知道大家看懂没有，给个意见。
#10
要把一种钢条重复取的情况考虑进去, 就是可重复的组合。和相同说明钢材利用率一样, 哪个先取都一样吧
#11
Michaelgs,请问DP是什么算法？
#12
To楼上 DP就是动态规划
#13
感觉这个像分段内存分配，呵呵
#14
It's called 'Bin Packing Problem'.
Check http://www.cs.gsu.edu/~cscskp/Algorithms/NP/node11.html
Check http://www.cs.gsu.edu/~cscskp/Algorithms/NP/node11.html
#15
完成了功能，现在效率差，钢条个数40个以上超级慢！！！
#16
呵呵
兄弟,这是背包问题
你可以查一些文献,或者是上网搜搜都可以.
我知道它肯定是背包问题
但是我从来没有学过.
我们老师和我说过.
它说的问题是这样的
有1米的直线,和10,20,30厘米的小线段
怎么放能放最多条数的直线.
兄弟,这是背包问题
你可以查一些文献,或者是上网搜搜都可以.
我知道它肯定是背包问题
但是我从来没有学过.
我们老师和我说过.
它说的问题是这样的
有1米的直线,和10,20,30厘米的小线段
怎么放能放最多条数的直线.