1次元配列解01リュックサック問題(各種大神の分析をまとめる)
3598 ワード
多くの筆記試験問題を経験したことがあるので、この多くの動態計画アルゴリズムを学ぶべきだと知っています.
問題の説明:
nと重量と価値がそれぞれWi,Viのものがあり、これらのものの中から総質量がCを超えないものを選び、総価値量を最大にするにはどうすればいいですか?
構想分析:
シーケンス番号
weight
value
1
2
3
4
5
6
7
8
9
10
a
2
5
0
5
5
8
8
13
13
14
16
16
b
3
3
0
1
3
8
8
9
11
11
14
14
c
5
6
0
1
1
8
8
9
9
9
14
14
d
4
8
0
1
1
8
8
9
9
9
9
9
e
2
1
0
1
1
1
1
1
1
1
1
1
この表は下から上へ左から右への順番で、e 2セルが最大許容重量2を表す場合、eアイテムのみが選択可能な場合、最大価値は1です.
c 3は最大許容重量が3であることを示し、c.d.e品のみが選択可能である場合、最大価値は1であり、dとeはいずれも3より大きいため、入れられない.
a 8の値は14ですが、どうやって手に入れますか?
01バックパックの状態変換方程式によると、f[i,j]=Max{f[i-1,j-wi]+Pi(j>=Wi)、f[i-1,j]}
f[i-1][j]はb[8]の値が11,f[i-1]、j-wiはb 6の値が9,9+5=14>11であるため、a 8の値は14となる.
原文アドレスを分析する:https://blog.csdn.net/mu399/article/details/7722810
リュックサックの容量がjの場合、すでにi個の品物が入っており、最大価値はd[i]d[j]である.
第iの物品がリュックサックよりも容量が大きい場合、置くことができないので、d[i][j]=d[[i-1][j];
第iの物品がリュックサックの容量より小さい場合、置かないと上式と同じで、置くとリュックサックの容量-第iの物品の品質は前のi-1の物品を詰めて、得られた最大の価値に第iの物品の価値を加えて、両者の大きい値が最適解であると判断します.d[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i])
スペースコストが大きいから小さいまでforループを構成すれば,アイテム数−1の値を直接1次元配列で保存できる.
リュックサックの容量がjの場合、すでにi個の品物が入っており、最大価値はd[j]である.
i番目の物品がリュックサックよりも容量が大きい場合、d[j]=d[j];
第iの物品がリュックサックの容量より小さい場合、置かないと上式と同じで、置くとリュックサックの容量-第iの物品の品質は前のi-1の物品を詰めて、得られた最大の価値に第iの物品の価値を加えて、両者の大きい値が最適解であると判断します.d[j]=max(dp[j],dp[j-w[i]]+v[i])
コードブログアドレス:https://blog.csdn.net/stack_queue/article/details/52734100
問題の説明:
nと重量と価値がそれぞれWi,Viのものがあり、これらのものの中から総質量がCを超えないものを選び、総価値量を最大にするにはどうすればいいですか?
構想分析:
シーケンス番号
weight
value
1
2
3
4
5
6
7
8
9
10
a
2
5
0
5
5
8
8
13
13
14
16
16
b
3
3
0
1
3
8
8
9
11
11
14
14
c
5
6
0
1
1
8
8
9
9
9
14
14
d
4
8
0
1
1
8
8
9
9
9
9
9
e
2
1
0
1
1
1
1
1
1
1
1
1
この表は下から上へ左から右への順番で、e 2セルが最大許容重量2を表す場合、eアイテムのみが選択可能な場合、最大価値は1です.
c 3は最大許容重量が3であることを示し、c.d.e品のみが選択可能である場合、最大価値は1であり、dとeはいずれも3より大きいため、入れられない.
a 8の値は14ですが、どうやって手に入れますか?
01バックパックの状態変換方程式によると、f[i,j]=Max{f[i-1,j-wi]+Pi(j>=Wi)、f[i-1,j]}
f[i-1][j]はb[8]の値が11,f[i-1]、j-wiはb 6の値が9,9+5=14>11であるため、a 8の値は14となる.
原文アドレスを分析する:https://blog.csdn.net/mu399/article/details/7722810
リュックサックの容量がjの場合、すでにi個の品物が入っており、最大価値はd[i]d[j]である.
第iの物品がリュックサックよりも容量が大きい場合、置くことができないので、d[i][j]=d[[i-1][j];
第iの物品がリュックサックの容量より小さい場合、置かないと上式と同じで、置くとリュックサックの容量-第iの物品の品質は前のi-1の物品を詰めて、得られた最大の価値に第iの物品の価値を加えて、両者の大きい値が最適解であると判断します.d[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i])
#include
#include
#include
#include
#include
using namespace std;
#define EMPTY
#define INF -65536
const int C=10;// capability
int n;//
int w[15],v[15];// ， weight, value
int dp[1000][C+1]={0};
int main(){
scanf("%d ",&n);
for(int i=1;i<=n;i++)scanf("%d",&w[i]);
for(int i=1;i<=n;i++)scanf("%d",&v[i]);
#ifdef EMPTY// ，
for(int i=0;i<=n;i++)dp[i][0]=0;
for(int i=0;i<=C;i++)dp[0][i]=0;
#else//
dp[0][0]=0;
for(int i=1;i<=C;i++)dp[0][i]=INF;
for(int i=1;i<=n;i++)dp[i][0]=INF;
#endif
for(int i=1;i<=C;i++){
for(int j=1;j<=n;j++){
dp[i][j]=w[j]<=i?max(dp[i][j-1],dp[i-w[j]][j-1]+v[j]):dp[i][j-1];
}
}
cout< スペースコストが大きいから小さいまでforループを構成すれば,アイテム数−1の値を直接1次元配列で保存できる.
リュックサックの容量がjの場合、すでにi個の品物が入っており、最大価値はd[j]である.
i番目の物品がリュックサックよりも容量が大きい場合、d[j]=d[j];
第iの物品がリュックサックの容量より小さい場合、置かないと上式と同じで、置くとリュックサックの容量-第iの物品の品質は前のi-1の物品を詰めて、得られた最大の価値に第iの物品の価値を加えて、両者の大きい値が最適解であると判断します.d[j]=max(dp[j],dp[j-w[i]]+v[i])
#include
#include
#include
#include
#include
using namespace std;
#define EMPTY
#define INF -65536
const int C=10;// capability
int n;//
int w[15],v[15];// ， weight, value
int dp[C+1];
int main(){
scanf("%d ",&n);
for(int i=1;i<=n;i++)scanf("%d",&w[i]);
for(int i=1;i<=n;i++)scanf("%d",&v[i]);
#ifdef EMPTY// ，
for(int i=0;i<=C;i++)dp[i]=0;
#else//
dp[0]=0;
for(int i=1;i<=C;i++)dp[i]=INF;
#endif
for(int i=1;i<=n;i++){
for(int j=C;j>0;j--){
dp[j]=w[i]<=j?max(dp[j],dp[j-w[i]]+v[i]):dp[j];// +v[i] dp[]
}
}
cout< コードブログアドレス:https://blog.csdn.net/stack_queue/article/details/52734100