背包問題系列之--01背包

問題描述:

????小偷深夜?jié)撊胍患抑閷毜曷乱模昀镉?件寶物娜氏,重量分別為W{1,3,2,4,5},對應(yīng)的價(jià)值為V{200,100,300,150,350 }硫戈。小偷隨身只攜帶了一個容量為5的背包荞膘,問小偷應(yīng)如何選擇才能使偷得寶物的價(jià)值最大罚随?

解題思路:

????一、建立動態(tài)規(guī)劃數(shù)組dp[i][j]羽资,表示小偷在背包總?cè)萘繛閖且只有前i件寶物可供選擇的情況下能帶走的最大價(jià)值淘菩;
????二、小偷將寶物一件一件的往袋子里裝屠升,對于每件物品i:小偷首先需要考慮潮改,攜帶的容量為j的包有可能裝的下這件寶物i嗎?換句話說腹暖,小偷除了寶物i以外其他寶物都不帶走汇在,他的包能不能裝下,即j>=w[i]是否成立脏答?
????????(1)如果條件j>=w[i]不成立糕殉,那么說明這件寶物i小偷無論如何也帶不走了亩鬼,此時他的能帶走的最大價(jià)值dp[i][j]=dp[i-1][j];
????????(2)如果條件j>=w[i]成立,即小偷是有能力帶走這件寶物的阿蝶,但這個狡猾的小偷又要思考了雳锋,寶物i我到底要不要拿走呢?如何取舍才能使得我背包的寶物總價(jià)值最大呢羡洁?
???????????????? i:如果小偷選擇不取寶物i玷过,那么此時背包的總價(jià)值與只有前i-1件寶物可選擇且背包總?cè)萘繛閖時能獲得的最大價(jià)值是一樣的,即dp[i][j]=dp[i-1][j]筑煮;
????????????????ii:如果小偷選擇寶物i辛蚊,那么此時背包的總價(jià)值為只有前i-1件寶物可選擇且背包總?cè)萘繛閖-w[i]時能獲得的最大價(jià)值再加上寶物i的價(jià)值v[i],即dp[i][j]=dp[i-1][j-w[i]]+v[i];
二者選擇總價(jià)值最大的即可真仲,接下來我們就按此思路擼代碼了......

Java代碼實(shí)現(xiàn):

public class Main {
    
    public static void main(String[] args) {
        int totalWeight=5;//背包容量
        Treasure[] packages={new Treasure(200, 1),
                            new Treasure(100, 3),
                            new Treasure(300, 2),
                            new Treasure(150, 4),
                            new Treasure(350, 5)};
        System.out.println(solution(packages, totalWeight));
    }

    public static int solution(Treasure[] treasures,int bagCapacity){
        int maxValue=-1;
        if(treasures==null||treasures.length==0||bagCapacity<=0){//參數(shù)合法性檢查
            maxValue=0;
        }else {
            int treasuresNum=treasures.length;
            //定義動態(tài)規(guī)劃數(shù)組dp[i][j],記錄有前i件物品可供選擇且背包容量為j時理科獲得的最大價(jià)值
            //這里加1是因?yàn)榭紤]了可選擇寶物數(shù)為0和背包容量為0的情況
            int dp[][]=new int[treasuresNum+1][bagCapacity+1];
            //初始化可選擇寶物數(shù)為0或者背包容量為0的情況,這個初始化可省略,數(shù)組定義時即自動初始化為0了
            for(int i=0;i<treasuresNum;i++){
                dp[i][0]=0;
                dp[0][i]=0;
            }
            //開始動態(tài)規(guī)劃袋马,由下而上
            int currentValue=0;
            int currentWeight=0;
            for(int i=1;i<=treasuresNum;i++){
                currentValue=treasures[i-1].getValue();//注意這里要減1
                currentWeight=treasures[i-1].getWeight();
                for(int j=1;j<=bagCapacity;j++){
                    if(currentWeight>j){//當(dāng)前考慮的寶物重量超過了背包最大容量
                        dp[i][j]=dp[i-1][j];
                    }else {//反之,小偷有能力帶走這塊寶物袒餐,但他需要考慮下是否價(jià)值最大
                        dp[i][j]=Math.max(dp[i-1][j], dp[i-1][j-currentWeight]+currentValue);
                    }
                }
            }
            maxValue=dp[treasuresNum][bagCapacity];
        }
        return maxValue;
    }
}

class Treasure{
    private int value;//價(jià)值
    private int weight;//重量
    public Treasure(int value,int weight) {
        this.setValue(value);
        this.setWeight(weight);
    }
    public int getValue() {
        return value;
    }
    public void setValue(int value) {
        this.value = value;
    }
    public int getWeight() {
        return weight;
    }
    public void setWeight(int weight) {
        this.weight = weight;
    }
}

復(fù)雜度分析

????以上方法的時間和空間復(fù)雜度均為O(VN),其中時間復(fù)雜度以不可再優(yōu)化谤狡,但空間復(fù)雜度還有在優(yōu)化的空間灸眼,優(yōu)化解法見參見我的另一篇博文背包問題系列之--01背包空間優(yōu)化解法

總結(jié)

????動態(tài)規(guī)劃現(xiàn)在是編程面試中的熱門,如果面試題是求一個問題的最優(yōu)解(通常是求最大值或者最小值)墓懂,而且該問題可分解成若干個子問題焰宣,并且子問題之間還有重疊的更小子問題,那么我們就可考慮使用動態(tài)規(guī)劃來解決這個問題了捕仔。

最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
  • 序言:七十年代末匕积,一起剝皮案震驚了整個濱河市,隨后出現(xiàn)的幾起案子榜跌,更是在濱河造成了極大的恐慌闪唆,老刑警劉巖,帶你破解...
    沈念sama閱讀 212,332評論 6 493
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件钓葫,死亡現(xiàn)場離奇詭異悄蕾,居然都是意外死亡,警方通過查閱死者的電腦和手機(jī)础浮,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 90,508評論 3 385
  • 文/潘曉璐 我一進(jìn)店門帆调,熙熙樓的掌柜王于貴愁眉苦臉地迎上來,“玉大人豆同,你說我怎么就攤上這事番刊。” “怎么了影锈?”我有些...
    開封第一講書人閱讀 157,812評論 0 348
  • 文/不壞的土叔 我叫張陵芹务,是天一觀的道長蝉绷。 經(jīng)常有香客問我,道長锄禽,這世上最難降的妖魔是什么潜必? 我笑而不...
    開封第一講書人閱讀 56,607評論 1 284
  • 正文 為了忘掉前任,我火速辦了婚禮沃但,結(jié)果婚禮上磁滚,老公的妹妹穿的比我還像新娘。我一直安慰自己宵晚,他們只是感情好垂攘,可當(dāng)我...
    茶點(diǎn)故事閱讀 65,728評論 6 386
  • 文/花漫 我一把揭開白布。 她就那樣靜靜地躺著淤刃,像睡著了一般晒他。 火紅的嫁衣襯著肌膚如雪。 梳的紋絲不亂的頭發(fā)上逸贾,一...
    開封第一講書人閱讀 49,919評論 1 290
  • 那天陨仅,我揣著相機(jī)與錄音,去河邊找鬼铝侵。 笑死灼伤,一個胖子當(dāng)著我的面吹牛,可吹牛的內(nèi)容都是我干的咪鲜。 我是一名探鬼主播狐赡,決...
    沈念sama閱讀 39,071評論 3 410
  • 文/蒼蘭香墨 我猛地睜開眼,長吁一口氣:“原來是場噩夢啊……” “哼疟丙!你這毒婦竟也來了颖侄?” 一聲冷哼從身側(cè)響起,我...
    開封第一講書人閱讀 37,802評論 0 268
  • 序言:老撾萬榮一對情侶失蹤享郊,失蹤者是張志新(化名)和其女友劉穎览祖,沒想到半個月后,有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體炊琉,經(jīng)...
    沈念sama閱讀 44,256評論 1 303
  • 正文 獨(dú)居荒郊野嶺守林人離奇死亡穴墅,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 36,576評論 2 327
  • 正文 我和宋清朗相戀三年,在試婚紗的時候發(fā)現(xiàn)自己被綠了温自。 大學(xué)時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片玄货。...
    茶點(diǎn)故事閱讀 38,712評論 1 341
  • 序言:一個原本活蹦亂跳的男人離奇死亡,死狀恐怖悼泌,靈堂內(nèi)的尸體忽然破棺而出松捉,到底是詐尸還是另有隱情,我是刑警寧澤馆里,帶...
    沈念sama閱讀 34,389評論 4 332
  • 正文 年R本政府宣布隘世,位于F島的核電站可柿,受9級特大地震影響,放射性物質(zhì)發(fā)生泄漏丙者。R本人自食惡果不足惜复斥,卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 40,032評論 3 316
  • 文/蒙蒙 一、第九天 我趴在偏房一處隱蔽的房頂上張望械媒。 院中可真熱鬧目锭,春花似錦、人聲如沸纷捞。這莊子的主人今日做“春日...
    開封第一講書人閱讀 30,798評論 0 21
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽主儡。三九已至奖唯,卻和暖如春,著一層夾襖步出監(jiān)牢的瞬間糜值,已是汗流浹背丰捷。 一陣腳步聲響...
    開封第一講書人閱讀 32,026評論 1 266
  • 我被黑心中介騙來泰國打工, 沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留寂汇,地道東北人病往。 一個月前我還...
    沈念sama閱讀 46,473評論 2 360
  • 正文 我出身青樓,卻偏偏與公主長得像健无,于是被迫代替她去往敵國和親荣恐。 傳聞我的和親對象是個殘疾皇子液斜,可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 43,606評論 2 350

推薦閱讀更多精彩內(nèi)容