01リュックサック問題ダイナミックプランニングc swiftデュアルバージョン

テーマ:n種類の物品とm重量を入れることができるリュックサックを与えて、物品の重量w、価値はpです.問:どのようにしてリュックサックをm重にして、最も価値のあるものを入れることができますか.
概念:なぜこのようなテーマはダイナミックな計画を使って、貪欲なアルゴリズムを使わないのですか.--個人的には,貪欲なアルゴリズムの各ステップの最適解は,最終的な答えが最適解ではない可能性があることを理解している.--動的計画では、前のステップまたは前のステップが最適解ではない場合に、現在のステップが最適解であることを解くことができます.
//このブロガーはとてもよく書いていて、考えがとてもはっきりしています.http://www.cnblogs.com/xy-kidult/archive/2013/03/25/2970313.html
include

                int c[10][10] = {0};
                void knapsack(int m,int n)
                {
                    int i,j,w[10],p[10];
                    for(i=1;ic[i-1][j]){///    c[i-1][j-w[i]]  w[i]   c[i-1][j]  w[i]      
                                
                                c[i][j] = c[i-1][j-w[i]]+p[i];///      w[i]    
                                
                            }else{///   ，     w[i]  ，    w[i]      
                                
                                c[i][j] = c[i-1][j];///    w[i]，   
                            }
                        }
                }
                int main()
                {
                    int m,n;int i,j;
                    printf("        ，     
");
                    
                    scanf("%d,%d",&m,&n);
                    
                    printf("            :
");
                    
                    knapsack(m,n);
                    
                    printf("
");
                    
                    for(i=0;i<=n;i++)
                        for(j=0;j<=m;j++)
                        {
                            printf("%d      ",c[i][j]);
                            if(j>m-1)printf("
");
                        }

                    printf("
");

                }

データを入力してくださいリュックサックの総重量を入力して、物品の総数量の10、3を入力して各物品の重量と価値を入力します:3、4 4、5、6 0 0 0 0 0 0 0 0 0 0 0 0 0 4 4 4 4 4 4 4 4 4 4 0 0 4 4 5 9 9 9 0 0 4 6 9 11
最適解値11
swuftバージョンはエンターテインメントimport UIKEのみ

                        var c =  [[0,0,0,0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0,0,0,0]]
                        ///       


                        ///m      ，n      

                        func knap(m:Int,n:Int){
                            
                            var w = [0,3,4,5,0,0,0,0,0,0,0,0,0]
                            var p = [0,4,5,6,0,0,0,0,0,0,0,0,0]
                            
                            for i in 1...n+1 {
                                
                                for j in 1...m+1{
                                    
                                    if j < w[i]{//    
                                        
                                        c[i][j] = c[i-1][j]
                                
                                    }else if(c[i-1][j-w[i]]+p[i]) > c[i-1][j]{ ///         ，      
                                        
                                        c[i][j] = c[i-1][j-w[i]]+p[i]
                                        
                                    }else{///              
                                        
                                        c[i][j] = c[i-1][j]
                                    }
                                    
                                }
                            }
                            
                        }


                         knap(10, n:3)

個人ブログ:www.liangtongzhuo.com