問題描述:
????小偷深夜?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ī)劃來解決這個問題了捕仔。