ダイナミックプランニングアルゴリズムの0-1リュックサック問題
2977 ワード
一、問題の説明
商品iの重量がwiであり、価値がviであるn種類の商品が与えられる.このn種類の商品を1つの容量cのリュックサックに入れて、それぞれの商品は入れるか入れないかを選択することができます.リュックサックを入れた商品をどのように選び、リュックサックの中で商品価値を最大にしますか.
二、問題分析
この問題のサブ問題を考慮し,その問題の解(x 1,x 2,......,xn)を一つの決定シーケンスとして考慮し,xiが1を取るか0を取るかを順次決定し,そのうち1はリュックサックに入れるか,0はリュックサックに入れないかを示す.
記v(i,j)は、前のi個の商品を容量jのリュックに入れることを示し、動的計画関数は
v(i,j)=v(i-1,j),j=max(v(i-1,j),v(i-1,j-wi)+vi)j>wi,リュックサック容量は物品iに入れることができ,この場合,(1)物品iを入れなければ前i−1個の商品を容量jのリュックに入れることができる,(2)物品iを入れると、前i−1個の商品のみを容量j−wiのリュックに入れることができる.この2つの場合のリュックにおける商品の最大価値を比較すればよい.
境界値v(i,0)=0は,前のi個の商品を容量0のリュックに入れることを示す.
v(0,j)=0は,上位0商品を容量jのリュックに入れることを示す.
三、アルゴリズムコード
四、完全なテストコード
五、運行結果
商品iの重量がwiであり、価値がviであるn種類の商品が与えられる.このn種類の商品を1つの容量cのリュックサックに入れて、それぞれの商品は入れるか入れないかを選択することができます.リュックサックを入れた商品をどのように選び、リュックサックの中で商品価値を最大にしますか.
二、問題分析
この問題のサブ問題を考慮し,その問題の解(x 1,x 2,......,xn)を一つの決定シーケンスとして考慮し,xiが1を取るか0を取るかを順次決定し,そのうち1はリュックサックに入れるか,0はリュックサックに入れないかを示す.
記v(i,j)は、前のi個の商品を容量jのリュックに入れることを示し、動的計画関数は
v(i,j)=v(i-1,j),j
境界値v(i,0)=0は,前のi個の商品を容量0のリュックに入れることを示す.
v(0,j)=0は,上位0商品を容量jのリュックに入れることを示す.
三、アルゴリズムコード
public static void knapsack(int [] w, int [] v, int c){
int n = w.length;
int [][] value = new int[n + 1][c + 1];
int [] selected = new int[n];
for(int i = 0; i <= c; i++){//
value[0][i] = 0;
}
for(int i = 0; i <= n; i++){//
value[i][0] = 0;
}
for(int i = 0; i <= n - 1; i++){// , 0 1 ，
for(int j = 1; j <= c; j++){
if(w[i] > j){
value[i + 1][j] = value[i][j];
}else{
value[i + 1][j] = Math.max(value[i][j], value[i][j - w[i]] + v[i]);
}
}
}
//
for(int i = n, j = c; i > 0;i--){
if(value[i][j] > value[i - 1][j]){
selected[i - 1] = 1;
j = j - w[i - 1];
}else{
selected[i - 1] = 0;
}
}
System.out.print(" (1 )：");
for(int i = 0; i <= n - 1; i++){
System.out.print(selected[i] + " ");
}
System.out.println();
//
System.out.println(" ：" + value[n][c]);
}四、完全なテストコード
public class package01 {
public static void main(String[] args) {
int [] w = new int[]{2,2,6,5,4};
int [] v = new int[]{6,3,5,4,6};
int c = 10;
knapsack(w, v, c);
}
public static void knapsack(int [] w, int [] v, int c){
int n = w.length;
int [][] value = new int[n + 1][c + 1];
int [] selected = new int[n];
for(int i = 0; i <= c; i++){//
value[0][i] = 0;
}
for(int i = 0; i <= n; i++){//
value[i][0] = 0;
}
for(int i = 0; i <= n - 1; i++){// , 0 1 ，
for(int j = 1; j <= c; j++){
if(w[i] > j){
value[i + 1][j] = value[i][j];
}else{
value[i + 1][j] = Math.max(value[i][j], value[i][j - w[i]] + v[i]);
}
}
}
//
for(int i = n, j = c; i > 0;i--){
if(value[i][j] > value[i - 1][j]){
selected[i - 1] = 1;
j = j - w[i - 1];
}else{
selected[i - 1] = 0;
}
}
System.out.print(" (1 )：");
for(int i = 0; i <= n - 1; i++){
System.out.print(selected[i] + " ");
}
System.out.println();
//
System.out.println(" ：" + value[n][c]);
}
}
五、運行結果
(1 )：1 1 0 0 1
：15