算法分析與設(shè)計(jì)01背包遞歸回溯

1、算法分析與設(shè)計(jì)實(shí)驗(yàn)03實(shí)驗(yàn)?zāi)康恼莆談?dòng)態(tài)規(guī)劃算法，簡(jiǎn)單0-1背包問(wèn)題；掌握最優(yōu)二叉搜索樹(shù)的算法。掌握貪心算法的貪心選擇性質(zhì)和最優(yōu)子結(jié)構(gòu)性質(zhì)；掌握最多活動(dòng)安排問(wèn)題，散裝背包問(wèn)題和最優(yōu)裝載問(wèn)題的貪心算法。實(shí)訓(xùn)內(nèi)容1、簡(jiǎn)單0-1背包問(wèn)題：給定一個(gè)背包，其容量是10千克，5件物品，其重量分別是4, 6，3, 5，8公斤；其價(jià)值分別是：9，3，6，13，15元，試根據(jù)動(dòng)態(tài)規(guī)劃算法給出 0-1背包問(wèn)題的最優(yōu)解以及相應(yīng)的求解過(guò)程（要求給出跳躍點(diǎn)的變化情況）。2、散裝背包問(wèn)題：給定一個(gè)背包，其容量是10千克，5件物品，其重量分別是4, 6, 3, 5, 8公斤；其價(jià)值分別是：9, 3, 6, 13, 15元，試

2、根據(jù)貪心算法給出散裝背 包問(wèn)題的最優(yōu)解以及相應(yīng)的求解過(guò)程。3、編寫(xiě)一個(gè)程序，完成如下要求：1）隨機(jī)生成10000個(gè)字符（字符包括：a, b, c, d, e和f），并將這10000個(gè)字符存 儲(chǔ)在名稱(chēng)為output.dat的文件中，并輸出該文件的長(zhǎng)度（單位：bit）。2）統(tǒng)計(jì)上述a, b, c, d, e和f各字符出現(xiàn)的次數(shù)。4、隨機(jī)選擇上題生成的2次結(jié)果，采用哈夫曼編碼對(duì)output.dat文件的各個(gè)字符進(jìn)行 編碼，并計(jì)算同原始o(jì)utput.dat文件的壓縮比率。/ 實(shí)驗(yàn) 3.cpp : Defines the entry point for the console application./

3、#include#includestring#include#includeusing namespace std;string get(int length)srand(unsigned)time(NULL);string s;for(int i=0;is;fps;fp.close();*/ofstream output;output.open(c:/output.dat);outputsendl;ifstream input;input.open(c:/output.dat);couts;for(int i=0;i100;i+)if(si=a) a+;if(si=b) b+;if(si=c) c+;if(si=d) d+;if(si=e) e+;if(si=f) f+;coutendl;couta 的數(shù)目aendl;coutb 的數(shù)目bendl;coutc 的數(shù)目