0-1バックパックの問題と点数バックパックの問題
19658 ワード
私達は文章の中で「貪欲アルゴリズム原理」:http://blog.csdn.net/ii1245712564/article/details/45369491の中で動態計画と欲張りアルゴリズムの違いに言及したことがあります.そして二つの経典の例:0-1リュックサック問題と分数リュックサック問題は0-1リュックサック問題が欲張りアルゴリズムで解決できないことを知っています.欲張りアルゴリズムは分数リュックサック問題の不二の選択です.今回は0-1リュックサック問題のダイナミック企画解法とスコアバックパック問題の貪欲アルゴリズムを重点的に実現します.
問題の説明
ここでは例を採用します.
私たちは三つの荷物と一つの容量が50のリュックサックを持っています.この三つのものはそれぞれa 1<10,60>で、a 2<20,100>で、a 3<30,120>です.
問題分析の点数リュックサック
簡単な期間のために、まずスコアバックパックの問題を分析します.欲張りなアルゴリズムを設計するなら、まず欲張りな策略を確定して、言い換えればどのように現在の状況の下で合理的な欲張りな選択をします.私たちはまず、それぞれのアイテムの単位の重さの価値を手に入れます.そうすると、私たちはカバンに入れる価値が最大になるように、貪欲な策略を設計します.私達の第一印象はきっと単位の重量が一番高いと思います.そして品物の中で二番目に高いのを選んで、バックパックがいっぱいになるまで類推します.
上の貪欲な選択の予想を証明します.
証明:
まず、A 1の最適解を持っていると仮定します.A 1の中で一番平均値が高いものを見つけます.A 1は商品の中で平均値が一番高いものをA 1で全部交換します.または部分的に交替します.A 2はv 1/w 1≧vm/wmですから、A 2の総価値がA 1の総価値より高いです.A 1には平均値が最も高いものが含まれています.
そこで、最適なサブ構造Si＝Sk＋akを得て、akはSiの中で最も平均値が高く、Skはakが残したものを選ぶ.
コードの設計の点数のリュックサックの問題
上記のように得点バックパック問題の最善の貪欲策に従って、毎回平均値が一番高いものを選びます.
/************************************************* * @Filename: fractionPackage.cc * @Author: qeesung * @Email: [email protected] * @DateTime: 2015-04-30 14:44:28 * @Version: 1.0 * @Description: ， **************************************************/
#include <iostream>
#include <utility>
#include <vector>
using namespace std;
#define PACKAGE_CAPACITY 50
/** * goodslist , * @param goodsList * @return */
unsigned fractionPackage(std::vector<pair<unsigned , unsigned> > goodsList)
{
unsigned valueSum=0;
unsigned capacitySum=0;
for (int i = 0; i < goodsList.size(); ++i)
{
//
if(goodsList[i].second + capacitySum >= PACKAGE_CAPACITY)
{
valueSum+=(PACKAGE_CAPACITY - capacitySum)*(goodsList[i].first/goodsList[i].second);
return valueSum;
}
valueSum+=goodsList[i].first;
capacitySum+=goodsList[i].second;
}
return valueSum;
}
int main(int argc, char const *argv[])
{
std::vector<pair<unsigned , unsigned> > goodsList;
goodsList.push_back(pair<unsigned , unsigned>(60,10));
goodsList.push_back(pair<unsigned , unsigned>(100,20));
goodsList.push_back(pair<unsigned , unsigned>(120,30));
cout<<"max value is : "<<fractionPackage(goodsList)<<endl;
while(1);
return 0;
}max value is 240
まず平均値が一番高いa 1をリュックサックに入れてa 2を入れます.この時A 3は全部リュックサックに入れることができないので、a 3の一部を入れてリュックサックに入ります.ここもよく分かります.つまり、荷物がいつもリュックサックでいっぱいになります.私たちが総価値を最高にするなら、平均の価値密度を高めるべきです.平均値が一番高い順にリュックサックに入れます.
問題分析の0-1バックパック問題
どうして私達は貪欲な計算方法で0-1リュックサックの問題を解決できませんか?反例を挙げるだけでいいです.私達はやはり前のように平均値が一番大きいのをリュックサックに入れて、a 1を入れて、a 2、a 3はもう入れられなくなりました.だからリュックサックの商品の総価値は60+100=160です.いいえ、a 2とa 3だけを入れると100+120=220になるので、ここは別の道を切り開くしかないです.一つのものは二つの選択しかありません.それはバックパックに入れるかどうかです.ですから、私たちは一つのものをリュックに入れるか入れないかを決めます.動的計画問題を解くには,最適なサブ構造と再帰的表現を見つけることがまず必要である.そこで、f(i,W)はi,i＋1,i＋2,…,n??????????t;n−i＋1個の商品で、リュックサックの容量はWの最適解です.まず私たちが決めなければならないのは、aiというものをバックパックに入れるかどうかです.この基準は何ですか?
f(i,W)={f(i＋1,W)f(i＋1,W−wi)+vi,wi>W,wi≦W
ダイナミック企画は再帰式があります.何でもいいです.
コード設計の0-1バックパックの問題
上の再帰表現があれば、コードを打ち始めます.私たちは上から下まで二つのダイナミック企画の方法を使って解決します.
/************************************************* * @Filename: zeroOnePackage.cc * @Author: qeesung * @Email: [email protected] * @DateTime: 2015-04-30 10:49:31 * @Version: 1.0 * @Description: 0-1 ， **************************************************/
#include <iostream>
#include <utility>
#include <vector>
using namespace std;
/** */
#define PACKAGE_CAPACITY 50
/** */
#define MAX_GOODS_NUM 10
/** */
bool packageChoose[MAX_GOODS_NUM];
/** maxValue[i][w] i w */
unsigned maxValue[MAX_GOODS_NUM][PACKAGE_CAPACITY];
unsigned dealZeroOnePackage(unsigned pos , unsigned weight , \
std::vector<pair<unsigned , unsigned> > & goodsList);
/** * goodslist * @param goodsList * @return */
unsigned zeroOnePackage(std::vector<pair<unsigned , unsigned> > goodsList)
{
for (int i = 0; i < MAX_GOODS_NUM; ++i)
{
packageChoose[i]=false;
}
dealZeroOnePackage(0,PACKAGE_CAPACITY,goodsList);
return maxValue[0][PACKAGE_CAPACITY];
}
/** * * @param pos * @param weight * @param goodsList * @return pos weight */
unsigned dealZeroOnePackage(unsigned pos , unsigned weight , \
std::vector<pair<unsigned , unsigned> > & goodsList)
{
if(pos >= goodsList.size() || weight == 0)
return 0;
if(maxValue[pos][weight] != 0 )
return maxValue[pos][weight];
//
unsigned temp1 = dealZeroOnePackage(pos+1,weight , goodsList);
if(weight >= goodsList[pos].second)
{
unsigned temp2 = dealZeroOnePackage(pos+1, weight - goodsList[pos].second, goodsList)+\
goodsList[pos].first;
unsigned retValue = temp1>temp2?temp1:temp2;
/** pos */
if(temp1 <= temp2)
{
packageChoose[pos]=true;
}
maxValue[pos][weight]= retValue;
return retValue;
}
else
{
maxValue[pos][weight]=temp1;
return temp1;
}
}
void printChoose()
{
for (unsigned i = 0; i < MAX_GOODS_NUM ; ++i)
{
if(packageChoose[i])
cout<<"a"<<i<<"\t";
}
cout<<endl;
}
int main(int argc, char const *argv[])
{
std::vector<pair<unsigned , unsigned> > goodsList;
goodsList.push_back(pair<unsigned , unsigned>(60,10));
goodsList.push_back(pair<unsigned , unsigned>(100,20));
goodsList.push_back(pair<unsigned , unsigned>(120,30));
cout<<"max value is : "<<zeroOnePackage(goodsList)<<endl;
printChoose();
while(1);
return 0;
}max value is 220 a 1 a 2
下から上へのダイナミック企画アルゴリズム
/************************************************* * @Filename: zeroOnePackage_v2.cc * @Author: qeesung * @Email: [email protected] * @DateTime: 2015-04-30 14:43:56 * @Version: 1.0 * @Description: ， **************************************************/
#include <iostream>
#include <utility>
#include <vector>
using namespace std;
#define MAX(a , b) ((a)>(b)?(a):(b))
/** */
#define PACKAGE_CAPACITY 50
/** */
#define MAX_GOODS_NUM 10
/** */
bool packageChoose[MAX_GOODS_NUM];
/** maxValue[i][w] i w */
unsigned maxValue[MAX_GOODS_NUM][PACKAGE_CAPACITY+1];
/** * goodslist * @param goodsList * @return */
unsigned zeroOnePackage(std::vector<pair<unsigned , unsigned> > goodsList)
{
for (int i = 0; i < MAX_GOODS_NUM; ++i)
{
packageChoose[i]=false;
}
for(int k = goodsList[goodsList.size()-1].second; k <= PACKAGE_CAPACITY ; ++k)
{
maxValue[goodsList.size()-1][k] = goodsList[goodsList.size()-1].first;
}
/** */
for (int i = goodsList.size()-2; i >=0 ; --i)
{
/** i , */
for(int k = goodsList[i].second; k <= PACKAGE_CAPACITY ; ++k)
{
maxValue[i][k] = MAX(maxValue[i+1][k] , maxValue[i+1][k - goodsList[i].second]+goodsList[i].first);
}
}
return maxValue[0][PACKAGE_CAPACITY];
}
void printChoose(unsigned pos , unsigned weight , \
std::vector<pair<unsigned , unsigned> > goodsList)
{
if(pos >= goodsList.size())
return;
if(maxValue[pos][weight] == maxValue[pos+1][weight - goodsList[pos].second]+goodsList[pos].first)
{
cout<<"a"<<pos<<"\t";
printChoose(pos+1 , weight - goodsList[pos].second , goodsList);
}
else
{
printChoose(pos+1 , weight , goodsList);
}
}
int main(int argc, char const *argv[])
{
std::vector<pair<unsigned , unsigned> > goodsList;
goodsList.push_back(pair<unsigned , unsigned>(60,10));
goodsList.push_back(pair<unsigned , unsigned>(100,20));
goodsList.push_back(pair<unsigned , unsigned>(120,30));
cout<<"max value is : "<<zeroOnePackage(goodsList)<<endl;
printChoose(0 , PACKAGE_CAPACITY , goodsList);
while(1);
return 0;
}max value is 220 a 1 a 2
動的プログラミングアルゴリズム間の違い
上の二つのアルゴリズムは動的計画アルゴリズムであるが、両者の間にはわずかな違いがある.
トップダウンアルゴリズムで:観測した.
unsigned temp1 = dealZeroOnePackage(pos+1,weight , goodsList);unsigned temp2 = dealZeroOnePackage(pos+1, weight - goodsList[pos].second, goodsList)+goodsList[pos].first;maxValue[pos][weight]= retValue; maxValueに対応するpos,weight位置だけを解いて、maxValueのこの二次元配列の他の位置を解決しません.ボトムアップアルゴリズムでは:このような循環式があることを観測した.
for (int i = goodsList.size()-2; i >=0 ; --i)
{
/** i , */
for(int k = goodsList[i].second; \
k <= PACKAGE_CAPACITY ; ++k)
{
maxValue[i][k] = MAX(maxValue[i+1][k] ,\
maxValue[i+1][k -\
goodsList[i].second]+goodsList[i].first);
}
}iに対応するこの行のほぼすべてのmaxVlaue配列の位置の値を解きましたが、私たちが使っているのは二つだけです.f(i,W)が要求されるなら、まずf(i＋1,W)とf(i＋1,W−wi)が分かりますから.しかし、この中のWとW−wiは不確定であり、配列maxValueのi＋1の行のすべての値を求めてこそ、上位ノードが任意に起動することができる.上から下までのアルゴリズムの欠点は、再帰的なコールではなく反復を採用することにあります.しかし、0-1バックパックの問題については、上から下までの求め方がより適していると思います.ここの
maxValue数です.グループは荷物の個数とバックパックの容量で決められています.もしバックパックの容量が500にアップグレードすれば、私は各ラインに500個のデータを計算するのではないですか?再帰すれば、自分の必要なデータだけを計算してもいいです.