裝箱問題貪心演算法

㈠ 求高手幫忙做一套演算法分析的題目。做好之後再加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，則答案錯誤。