動的計画解0-1リュック問題(JAVA)
4542 ワード
問題の説明
n種類の物品と1つのリュックサックを与えて、物品iの重量はwiで、価値viで、リュックサックの容量はCで、どのようにリュックサックの中に入る物品を選んで、リュックサックの中に入る物品の総価値を最大にしますか?各アイテムについて、完全にロードするか、ロードしないかを選択できます.1つのアイテムは最大1回ロードされます.
対価マトリクスmと状態方程式の定義
m[i][j] i:物品番号、取値範囲0~n-1、ここではi~n-1物品から選択する を示す. j:リュックサック利用可能容量 m[i][j]:リュックサックの利用可能容量がjの場合、i~n-1アイテムから選択し、問題の最適代価はm[i][j] である.
じょうたいほうていしき
n-1の番号のものから、初期番号が0になるまで考える
m[n-1][j] = 0, 0 ≤ j
m[n-1][j] = v[n], j ≥w[n-1]
m[i][j]=m[i+1][j], 0≦jm[i][j] = max{m[i+1][j],m[i+1][j-w[i]]+v[i]}, j ≥ w[i]
m[i][j]=max{m[i+1][j],m[i+1][j-w[i]+v[i]}:現在の品物は入れず、状況はm[i+1][j]の場合と同じで、リュックサックの容量は変わらない.現在のアイテムをリュックサックに入れるかどうかを決定します.新しい容量=元の容量-現在のアイテムの重量、現在の価値+=現在のアイテムの価値
例を挙げる
コード#コード#
転載先:https://juejin.im/post/5d4d50d85188256f672b954e
n種類の物品と1つのリュックサックを与えて、物品iの重量はwiで、価値viで、リュックサックの容量はCで、どのようにリュックサックの中に入る物品を選んで、リュックサックの中に入る物品の総価値を最大にしますか?各アイテムについて、完全にロードするか、ロードしないかを選択できます.1つのアイテムは最大1回ロードされます.
対価マトリクスmと状態方程式の定義
m[i][j]
じょうたいほうていしき
n-1の番号のものから、初期番号が0になるまで考える
m[n-1][j] = 0, 0 ≤ j
m[n-1][j] = v[n], j ≥w[n-1]
m[i][j]=m[i+1][j], 0≦j
m[i][j]=max{m[i+1][j],m[i+1][j-w[i]+v[i]}:現在の品物は入れず、状況はm[i+1][j]の場合と同じで、リュックサックの容量は変わらない.現在のアイテムをリュックサックに入れるかどうかを決定します.新しい容量=元の容量-現在のアイテムの重量、現在の価値+=現在のアイテムの価値
例を挙げる
：n=3,w={4,1,5},v=w,C=9
m(3,9)=4=m(3,8~4) m(3,3~0)=0
m(2,9)=max(m(3,9),m(3,8)+1)=5 m(2,4)=max(m(3,4),m(3,3)+1)=4
m(1,9)=max(m(2,9),m(2,4)+5)=9
コード#コード#
public class KnapsackProb {
/**
* @param args
* ： ： ； ： （ 0 ）
*/
public static void main(String[] args) {
int n=5,C=10;//
int[] w= {2,2,6,4,5};//
int[] v= {6,3,5,4,6};//
// int n=3,C=9;
// int[] w={1,4,5};int[] v=w;
int[][] m=new int[n][C+1];
//m
// n-1
for(int j=0;j<=C;j++) {
if(j1])
m[n-1][j]=0;
else m[n-1][j]=v[n-1];
}
// n-2~0
for(int i=n-2;i>=0;i--) {
for(int j=0;j<=C;j++) {
if(j//
m[i][j]=m[i+1][j];
else m[i][j]=Math.max(m[i+1][j], m[i+1][j-w[i]]+v[i]);// ，
}
}
System.out.println(m[0][C]);//
// ： i m[i][j]>m[i+1][j]
int j=C;
// 0~n-2
for(int i=0;i1;i++) {
if(m[i][j]>m[i+1][j]) {
System.out.print(i+" ");
j=j-w[i];
}
}
if(m[n-1][j]!=0)
System.out.print(n-1);
}
}
転載先:https://juejin.im/post/5d4d50d85188256f672b954e