装箱问题贪心算法

㈠ 求高手帮忙做一套算法分析的题目。做好之后再加100。

如何选择排序、矩阵相乘、树和图算法的时间复杂性计量单位？
排序：排序的循环次数（或递归次数）。
矩阵相乘：做实数乘法的次数。
树：搜索的次数。
图：同树。
算法有几种基本结构？各种结构的时间复杂度的计算规则？
3种
顺序结构：T(n)=O(c)
选择结构：T(n)=O(c)
循环结构：T(n)=O(n)
最坏情况下的时间复杂性和平均情况下的时间复杂性的定义？
在规模n的全部输入中，可以找寻执行一个算法所需的最大时间资源的量，这个量称为对规模n的输入，算法的最坏情况时间复杂性。
对规模都为n的一些有限输入集，执行算法所需的平均时间资源的量称为平均情况下的时间复杂性。
为什么选择时间复杂度的渐进性态评价算法？
因为在规模较小的时候无法客观体现一个算法的效率。
解释f(n)=O(g(n))的意义。
若f(n)和g(n)是定义在正整数集合上的 两个函数，则f(n)=O(g(n))表示存在正的常数C和n0 ,使得当n≥n0时满足0≤f(n)≤C*g(n)。
简述之就是这两个函数当整型自变量n趋向于无穷大时，两者的比值是一个不等于0的常数。
有效算法和无效算法的划分原则？
区分在于问题是否能够精确求解。
用分治法设计算法有什么好处？为什么描述分治算法需要使用递归技术？
分治法可以将问题分为许规模更小的子问题，这些子问题相互独立且与原问题相同。使用递归技术，虽然一些简单的循环结构替代之，但是复杂的问题，比如二阶递归是无法替代的。
归并排序算法和快速排序算法划分子问题和合并子问题的解的方法各是是怎样的？
归并排序算法：
划分子问题：每次分成2个大小大致相同的子集和
合并子问题：将2个排好序的子数组合并为一个数组
快速排序算法：对输入的子数组a[p:r]
划分子问题：划分为a[p:q-1],a[q]和a[q+1:r]使a[p:q-1]任意元素小于a[q]，a[q+1:r] 任意元素大于a[q]
合并子问题：不需要（因为划分过程就已经排序完成了）
简述二分检索（折半查找）算法为什么比顺序查找的效率高？
对于二分搜索 最坏情况为O(logn)时间完成
而顺序查找 需要O(n)次比较
显然二分搜索效率高
贪心法的核心是什么？
贪心算法是通过一系列选择得到问题的解，它所作出的选择都是当前状态下的最佳选择。
背包问题的目标函数是什么？背包问题贪心算法的最优量度是什么？算法是否获得最优解？ 用贪心算法解0/1背包问题是否可获得最优解？
Max=∑Vi*Xi (V是价值X取1，0表示装入或不装)
每次选取单位重量价值最高的
不一定是最优解

情况不妙啊 LZ还要继续否。。。
早知发邮件了。。。

㈡ 分析用动态规划和贪心算法求解背包问题的差异

动态规划本质是以空间换时间，算出了所有可行解的值域。

而贪心算法，每次选则最优的，而结果未必最优。
举个简单例子。
背包能装8kg,有3个物品，分别为3kg,4kg,5kg
动态规划，是计算，3+4， 3+5，得出解，最大的是3+5=8kg
贪心算法，是选择，第一次选最大的：5kg<8kg，第二次选则剩下的最大的4kg，4+5>8,故而解为5kg。

㈢ 用贪心算法解决背包问题

用贪心算法解决背包问题，首先要明白，结果不一定是全局最优的。对于贪心法而言，首先步骤是找到最优度量标准，我这里的算法采用的最优度量标准是： 收益p/重量w 的值最大者优先放入背包中，所以有算法如下：void GreedyKnapsack(float * x){ //前置条件：w[i]已按p[i]/w[i]的非增次序排列 float u=m; //u为背包剩余载重量，初始时为m for(int i=0;i<n;i++) x[i]=0; //对解向量x初始化 for(i=0;i<n;i++){ //按最优度量标准选择的分量 if(w[i]>u) break; x[i]=1.0; u=u-w[i]; } if(i<n) x[i]=u/w[i];}

㈣ 将最优装载问题的贪心算法推广到2艘船的情形，贪心算法仍能产生最优解吗

贪心算法不能产生最优解。

两艘船的装载问题，是先装完第一艘，再装第二艘，所以就必须把第一艘尽可能的装满，才能使总的装载量更多。

对于一个具体问题，要确定它是否具有贪心选择的性质，必须证明每一步所作的贪心选择最终能得到问题的最优解，通常可以首先证明问题的一个整体最优解，是从贪心选择开始的，而且作了贪心选择后，原问题简化为一个规模更小的类似子问题。

(4)装箱问题贪心算法扩展阅读：

两艘船的装载问题需要用的是回溯法，有了问题的解空间后，还需要将解空间有效地组织起来，使得回溯法能方便地搜索整个解空间，通常将解空间组织成树或图的形式。

如果在当前的扩展结点处不能再向纵深方向移动，则当前的扩展结点就成为死结点。此时应往回移动(回溯)至最近的一个活结点处，并使其成为当前的扩展结点。回溯法以上述工作方式递归地在解空间中搜索，直至找到所要求的解或解空间中已无活结点时为止。

此外，贪心算法的每一次操作都对结果产生直接影响，而动态规划则不是。贪心算法对每个子问题的解决方案都做出选择，不能回退；动态规划则会根据以前的选择结果对当前进行选择，有回退功能。

㈤ C++贪心算法问题：快递装箱

import java.util.Arrays;
import java.util.Comparator;
//装箱问题，贪心算法
public class Enchase {
public void test1() {
Integer[] boxs={34,6,40,2,23,12,12};

㈥ 为什么贪心算法不能解0-1背包问题

贪心算法解决背包问题有几种策略：
(i)一种贪婪准则为：从剩余的物品中，选出可以装入背包的价值最大的物品，利用这种规则，价值最大的物品首先被装入（假设有足够容量），然后是下一个价值最大的物品，如此继续下去。这种策略不能保证得到最优解。例如，考虑n=2, w=[100,10,10], p =[20,15,15], c = 105。当利用价值贪婪准则时，获得的解为x= [ 1 , 0 , 0 ]，这种方案的总价值为2 0。而最优解为[ 0 , 1 , 1 ]，其总价值为3 0。
(ii)另一种方案是重量贪婪准则是：从剩下的物品中选择可装入背包的重量最小的物品。虽然这种规则对于前面的例子能产生最优解，但在一般情况下则不一定能得到最优解。考虑n= 2 ,w=[10,20], p=[5,100], c= 2 5。当利用重量贪婪策略时，获得的解为x =[1,0], 比最优解[ 0 , 1 ]要差。
(iii)还有一种贪婪准则，就是我们教材上提到的，认为，每一项计算yi=vi/si,即该项值和大小的比，再按比值的降序来排序，从第一项开始装背包，然后是第二项，依次类推，尽可能的多放，直到装满背包。
有的参考资料也称为价值密度pi/wi贪婪算法。这种策略也不能保证得到最优解。利用此策略试解n=

㈦ Python 如何将长度不同的字符串尽量均匀地分配到N个文件中每一行的字符串作为整体，不能打散。

背包问题的一个变种。或者说是一维装箱算法。

你将每一行字符串想象为一个物品，字符串的长度就是这个物品的大小。每个文件相当于不同的箱子，箱子的大小是固定的，装入的物品体积之和不能超过箱子的总容量。

问题就是：如何使用尽可能少的箱子来装入所有的物品，或者：如果使尽可能多的箱子空间利用率更高，以及类似的相关问题。

这类问题的答案不是一个简单的数字，它需要给出一个策略：物品1...n分别装入箱子1...m(m<=n).

对于二维装箱或三维等，区别主要在于解法的复杂度，但一个解法一般来说其思路是可以从一维扩展到二维或者三维的。

这类问题目前来说，没有全局最优解（即，没有一个算法能确保在所有情况下均能得到最好的结果），但可以得到局部最优解。算法有多种，如最常见的贪心算法，或动态规划。

贪心算法的思路比较简单：把所有的物品从大到小排好序，拿一个箱子，尝试装入最大的物品，如果不能装入，就尝试装入小一些的物品，如此循环，直到所有物品装入所有箱子。

算法很简单，但很多时候得到的结果并不理想。

㈧ 你好，我生活中遇到的问题，是关于c语言，或c++编程的，希望您能看一下

你这个问题属于运筹学中典型的装箱问题，是运筹学中的整数规划问题，属NP难题：
设有编号1-n的n种物品，体积分别为v1、v2、v3.。。。。。vn，将这N种物品装入容积都为V的若干箱子内，约定这n种物品的体积vi都不超V，即对于1≤i≤n，有0≤vi≤V。装箱问题要求使装尽这n种物品的箱子数最少。采用贪心算法能找到近似解。
常用解法：
1、首次适应算法：拿到一个物品，从第一个箱子找，找到第一个能在装进它的箱子。
2、最佳适应算法：拿到一个物品，每个箱子都找遍，找到一个剩余空间最小且能放进它的箱子。
这两个都属线性算法，复杂度都不算太高，能找到比较好的近似解，但编程都有一定难度，需要花时间考虑数据结构，比较啰嗦。
等我有空了帮写一个，现在周末休息。
找到一个Pascal代码和一个C代码，都没验证过，你可以参考参考：
Pascal代码：http://..com/link?url=-GdjgCNmSjGmrtEwgVqId_sOoFtQNExk8H9NFHnNtnEsW_
C代码：http://blog.csdn.net/cxxsoft/article/details/935688

㈨ 【急】C语言的箱问题

这是动态规划问题的典型问题

你可以搜一下动态规划解决“装箱问题”和“背包问题”，看一下思想就明白了。

祝顺利解决。

【2001年普及组4】装箱问题

Time Limit:1000MS Memory Limit:65536K
Total Submit:512 Accepted:251

Description

有一个箱子容量为v(正整数，o≤v≤20000)，同时有n个物品(o≤n≤30)，每个物品有一个体积 (正整数)。要求从m个物品中，任取若千个装入箱内，使箱子的剩余空间为最小。
[样例]
输入：
24 一个整数，表示箱子容量
6 一个整数，表示有n个物品
8 接下来n行，分别表示这n个物品的各自体积。
3
12
7
9
7
输出：
0 一个整数，表示箱子剩余空间。

Input

第一行为箱子容量为v；第二行为物品数；以下n行分别为每个物品的体积；

Output

箱子剩余空间

Sample Input

24
6
8
3
12
7
9
7

Sample Output

0
*/
/*
动态规划，设：a[i,j] 表示选前i个物品刚好能装满 j 空间,则有：
a[i,j] = a[i-1][j] or a[i-1][j-v[i]] j>v[i]
a[i,0] = 0 ;
不过，这题有点特殊：
就是：
a[i,j]只与: i-1有关
所以可以降到一维...
*/
#include <stdio.h>
#include <string.h>

#define MAX 20001

int main(void)
{
int m,n,tv,v,i,j,k ;
int a[MAX] ={0} ;
a[0] = 1;
scanf("%d",&v) ;
scanf("%d",&n) ;

for(i=1 ; i<= n ; i++)
{
scanf("%d",&tv);
for(j=v ; j>=tv ; j--)
if(!a[j])
a[j] = a[j-tv] ;
}
m = v ;
while ( a[m] == 0)
m -- ;
printf("%d ",v-m) ;

return 0 ;
}

㈩ 贪心算法 部分背包问题

[背包问题]有一个背包，背包容量是M=150。有7个物品，物品可以分割成任意大小。
要求尽可能让装入背包中的物品总价值最大，但不能超过总容量。
物品 A B C D E F G
重量 35 30 60 50 40 10 25
价值 10 40 30 50 35 40 30
分析：
目标函数： ∑pi最大
约束条件是装入的物品总重量不超过背包容量：∑wi<=M( M=150)
（1）根据贪心的策略，每次挑选价值最大的物品装入背包，得到的结果是否最优？
（2）每次挑选所占重量最小的物品装入是否能得到最优解？
（3）每次选取单位重量价值最大的物品，成为解本题的策略。 ?
值得注意的是，贪心算法并不是完全不可以使用，贪心策略一旦经过证明成立后，它就是一种高效的算法。
贪心算法还是很常见的算法之一，这是由于它简单易行，构造贪心策略不是很困难。
可惜的是，它需要证明后才能真正运用到题目的算法中。
一般来说，贪心算法的证明围绕着：整个问题的最优解一定由在贪心策略中存在的子问题的最优解得来的。
对于例题中的3种贪心策略，都是无法成立（无法被证明）的，解释如下：
（1）贪心策略：选取价值最大者。反例：
W=30
物品：A B C
重量：28 12 12
价值：30 20 20
根据策略，首先选取物品A，接下来就无法再选取了，可是，选取B、C则更好。
（2）贪心策略：选取重量最小。它的反例与第一种策略的反例差不多。
（3）贪心策略：选取单位重量价值最大的物品。反例：
W=30
物品：A B C
重量：28 20 10
价值：28 20 10
根据策略，三种物品单位重量价值一样，程序无法依据现有策略作出判断，如果选择A，则答案错误。