【アルゴリズム復習三】アルゴリズム設計技術と最適化――各種リュックサック問題まとめ

5481 ワード

一,計算方の策略は応用します.
       1)リュックサックについて
             利益との関係によって分ける.
                    •利益に関係のないリュックサックの問題
                    •利益に関するリュックサック問題
             荷物にリュックサックを入れたのはどれぐらいですか?
                   •リュックサックの問題の一部
                   •0-1バックパック問題
       2)バックパック問題の解決策は、必要に応じて異なります.
                 •貪欲法、回想法、分岐限界法、ダイナミック企画
                • 再帰的または非再帰的に解く
バックパック問題の展示
        1)リュックサック問題1
             • 問題の説明:与えられたn種の物品の中からm個を選んで、その重さの和とTの差の絶対値を最小にします.
            例えば、n=9,m=3,T=500グラムです.
             • 問題分析1:三重循環、列挙法を採用する.
               データの変化過程:
                      (1,2,3)(1,2,4)…(1,2,9)
                      (1,3,4)(1,3,5)…(1,3,9)…(1,8,9)
                     (2,3,4)(2,3,5)…(2,3,9)…(7,8,9)
            • アルゴリズム1分析   時間の複雑さはO(n 3)である.
            • ソース:

#include <iostream>
using namespace std;
int main()
{
	int a[9]={1,2,3,4,5,6,7,8,9};
	int m=3;
	int T=5;
	int diff;
	int mindiff=999;
	int tempi,tempj,tempk;
	for(int i=0;i<9;++i)
	{
		for(int j=i+1;j<9;++j)
		{
			for(int k=j+1;k<9;++k)
			{
				diff=(a[i]+a[j]+a[k]-T>0?a[i]+a[j]+a[k]-T:T-(a[i]+a[j]+a[k]));
				if(mindiff>diff)
				{
					mindiff=diff;
					tempi=i;
					tempj=j;
					tempk=k;
				}		
			}	
		}
	}
	
	cout<<"select number is:"<<a[tempi]<<" "<<a[tempj]<<" "<<a[tempk]<<endl;
	cout<<"Sunm :"<<a[tempi]+a[tempj]+a[tempk]<<endl;
	cout<<"mindiff: "<<mindiff<<endl;
	
}

            2)リュックサック問題2
                 • 問題の説明:与えられたn種の物品と重さはMバックパックです.物品iの重さはwiです.リュックサックに入れるものはどうやって選ぶべきですか?リュックに入れるものの総重量が一番重いです.問題のすべての解を探し出す.例えば、M=10の場合、各商品はそれぞれ｛5,2,3.5,1.7,1,5.1｝です.
                 •問題分析2:多重サイクル、列挙法を採用する.
                 • ソース:

#include <iostream>
using namespace std;
int main()
{
	double a[6]={5,2,3.5,1.7,1,5.1};
	double M=10;
	double max=0;
	double temp;
	for(int i1=0;i1<=1;++i1)
	{
		for(int i2=0;i2<=1;++i2)
		{
			for(int i3=0;i3<=1;++i3)
			{
				for(int i4=0;i4<=1;++i4)
				{
					for(int i5=0;i5<=1;++i5)
					{
						for(int i6=0;i6<=1;++i6)
						{
							temp=a[0]*i1+a[1]*i2+a[2]*i3+a[3]*i4+a[4]*i5+a[5]*i6;
				                   if(temp<=M&&max<temp)
				              		max=temp;
						}
					}
				}
			}	
		}
	}
	
	cout<<max<<endl;
}

改善:10進数をバイナリに変換することができます.例えば、000001は一つだけを表し、000011は二つを選ぶことを表す.サイクルの回数は2`6です

       3)リュックサック問題3
            • 問題の説明:与えられたn種の物品と重さはMバックパックです.物品iの重さはwiです.リュックサックに入れた荷物はどうやって選ぶべきですか?リュックに入れた荷物の総重量はちょうどMで、問題のすべての解を探し出します.例えば、M=10の場合、それぞれの物品は｛1、8、4、3、5、2｝であり、4グループの解(1、4、3、2)(1、4、5)(8、2)(3、5、2)を得ることができる.
            • 問題の分析
              回溯法を利用して、一つ一つ試してみて、荷物を順次リュックに入れて、もしリュックサックの重さを超えるならば、現在選んだものを捨てて、次のものを選んで、このように繰り返して、すべての解を探し出すまで、あるいは解けません.
              物品のシーケンス｛1,8,4,5,2｝の番号が1、2、3、4、5、6であると仮定して、この問題の中で物品の取り出しの順序と読み込みの順序は正反対であり、スタックを使用して解を説明することができると考えられる.
             • ソース

#include <iostream>
#include <stack>
using namespace std;
int w[6]={1,8,4,3,5,2};
int M=10;
	
void StackTraverse(stack<int> S)
{
	cout<<"      ："<<endl;
	while(!S.empty())
	{ 
		cout<<w[S.top()]<<endl;
		S.pop();
	}
}
void knapsack(int w[],int M, int n)
{   
    stack<int> S;     
	int k=0;  //  1     	
    while(!S.empty()||k<n)
	{
 		while(M>0&&k<n)
	 	{
			if(M-w[k]>=0)
 			{
 				S.push(k);
	    		M-=w[k];			 	    	
         	}
              k++;
       }           
        if (M==0)		  
		   StackTraverse(S); //     ，           
		 
	    k=S.top()+1;//     
		M+=w[S.top()];//  M  
       	S.pop();//      ，   	      
   }
}
int main()
{	
	knapsack(w,M,6);
	
	return 0;
}

            4)リュックサック問題4--利益リュックサック問題の貪欲アルゴリズム
                  • 問題の説明:与えられたn種の物品とリュックサック.物品iの重さはwiで、その価値はpiで、リュックサックの容量はMです.リュックサックに入れるものはどうやって選ぶべきですか?
• 欲張り分析
物の中から単価が一番高いものを選ぶたびに、その重さがリュックサックの重さより小さいなら、リュックサックに入れることができます.そして、私たちは一番いい問題に直面しました.同じリュックサックの問題です.でも、この時の容量はMが減りました.したがって、バックパックの問題も明らかに最適なサブ構造特性を持っている.欲張りアルゴリズムで解くことができます.　
•   欲張りでリュックサックの問題を解く4の基本的な手順
                   (1)まず各物品単位の重量の価値pi/wiを計算する.
                   (2)n種のものの総重量が総重量Mより小さい場合、全部リュックに入れるだけでいいです.
                   (3)そうでないと、荷物単位の重量価値によって、高いから低いまでリュックサックに入れる.
                   (4)カバンの中の荷物の総重量がMを超えていない場合は、この戦略に従ってリュックサックが満杯になるまで続けます.
                   (5)最後に入れたのは物品の一部かもしれません.
5)リュックサック問題5–0-1リュックサック問題の動態計画法
問題の説明:与えられたn種の物品とリュックサック.物品iの重さはwiで、その価値はpiで、リュックサックの容量はMです.リュックサックに入れるものはどうやって選ぶべきですか?(アイテムをゼロにしてはいけません.)詳細はブログを参照してください.http://blog.csdn.net/tianshuai11/article/details/7533317

6)リュックサック問題6–0-1リュックサック問題の分岐限界法
• 問題の説明:与えられたn種の物品とリュックサック.物品iの重さはwiで、その価値はpiで、リュックサックの容量はMです.リュックサックに入れるものはどうやって選ぶべきですか?(物品をゼロにすることは許されません)そして、積み込みされたものの方案を示す行列式分岐限界法です.
• アルゴリズム解析
アルゴリズムの計算時間の上限はO(2`n)です.
•   0-1リュックサックの問題に対して、貪欲な選択が最適化されないのは、最終的にリュックサックを詰められる保証がないからです.部分が空いているリュックサックの空間は一キロ当たりのリュックのスペースの価値を下げました.

•
実は、考えています.
0-1
リュックサックの問題は、そのものを選択するか、そのものを選択しないかによる最終案を比較して選択してください.これにより多くの相互に重なり合うサブ問題が導出される.これはまさにこの問題を動的計画アルゴリズムで解くことができるもう一つの重要な特徴である.

一つのDense SIFTアルゴリズムのmatlabは実現します.

AndroidのCamera写真補間アルゴリズム