• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            voip
            風的方向
            厚德致遠,博學敦行!
            posts - 52,comments - 21,trackbacks - 0
                           在別人眼里輕而易舉的的事情落在自己身上可能比登天還要難!!
                            0-1背包問題:給定n中物品和一個背包。物品i的重量是wi,價值為vi,背包的容量為c。問如何選擇裝入背包中的武平,使得裝入背包中的物品價值最大?
                           書上有一行行的算式,證明最優子結構性質和構造遞歸關系。我沒怎么看明白最優子結構,但是我能看懂遞歸關系式??!我記得當時老師叫我們的時候我自己想了好幾天才想明白這個遞歸式,但是始終覺得有點虛,借此我再寫一下!
                           設數組m(i,j)代表背包容量為j,可選物品為i,i+1,..n時的最優解(這里的最優解指的是選擇方案,并非正真的最優值),顯然m(1,c)是0-1背包問題的解(這里是書上的錯誤,應該是m[1]中的最大值?。∥液髞聿虐l現的。。)。這種定義雖然比較拗口,但是還是可以接受的,其實我們也可以這么定義m[i][j],代表背包容量為j,當前選擇物品為a[i]時的最優解,顯然m數組中第n行的最大值是0-1背包問題的解??!

            第一種定義的遞歸式如下:
                                                           1
               m[i][j]=max{m[i+1][j],m[i+1][j-wi]+vi}  j>=wi;    m[i][j]=m(i+1,j)   0<=j<wi

            第二種定義的遞歸式如下:
                                          0                  1
               m[i][j]=max{m[i-1][j],m[i-1][j-wi]+vi}    j>=wi;    m[i][j]=m(i-1,j)   0<=j<wi

            代碼如下:
            #include<stdio.h>
            #include
            <iostream>
            #include
            <string.h>
            using namespace std;

            int max(int x,int y)
            {
                
            if(x>y)
                    
            return x;
                
            return y;
            }


            int min(int x,int y)
            {
                
            if(x>y)
                    
            return y;
                
            return x;
            }


            template 
            <class Type>     
            void Knapsack(Type *v,int *w,int c,int n,Type m[][20])//構造m,最優取舍方案函數??!
            {
                
            int i,j;
                
            int jMax=min(w[n]-1,c);

                
            for(j=0;j<=jMax;j++)
                    m[n][j]
            =0;

                
            for(j=w[n];j<=c;j++)
                    m[n][j]
            =v[n];

                
            for(i=n-1;i>=1;i--)
                
            {
                    jMax
            =min(w[i]-1,c);

                    
            for(j=0;j<jMax;j++)
                        m[i][j]
            =m[i+1][j];

                    
            for(j=w[i];j<=c;j++)
                        m[i][j]
            =max(m[i+1][j],m[i+1][j-w[i]]+v[i]);
                }


            /*    m[1][c]=m[2][c];
                if(c>=w[1])
                    m[1][c]=max(m[1][c],m[2][c-w[1]]+v[1]);
            */
            //這里是書上的一個錯誤,并不是m[1][c]就是0-1背包問題的解,事實上m[1]上的所有解都有可能!!
                
            //所以還是應該把m[1]上的所有最優構造都算出來,然后去最大值
            }


            template 
            <class Type>                            //構造x數組函數
            void Traceback(Type m[][20],int *w,int c,int n,int x[])
            {
                
            int i;
                
            for(i=1;i<n;i++)
                
            {
                    
            if(m[i][c]==m[i+1][c])
                        x[i]
            =0;
                    
            else
                    
            {
                        x[i]
            =1;
                        c
            -=w[i];
                    }

                }


                x[n]
            =(m[n][c])?1:0;
            }

            int main()
            {
                
            int w[10],v[10],x[10],m[20][20],c,n,max,c0;
                
            int i,j;

                
            while(scanf("%d",&n)!=EOF)
                
            {
                    max
            =0;
                    memset(m,
            0,sizeof(m));
                    
            for(i=1;i<=n;i++)
                    
            {
                        scanf(
            "%d %d",&w[i],&v[i]);
                    }

                    scanf(
            "%d",&c);

                    Knapsack(v,w,c,n,m);    
            //構造最優取舍方案
                    
                    
            for(i=1;i<=c;i++)
                    
            {
                        
            if(m[1][i]>max)
                        
            {
                            max
            =m[1][i];
                            c0
            =i;
                        }

                    }

                    Traceback(m,w,c0,n,x);        
            //構造x數組
                    
                    printf(
            "最優矩陣如下:\n");
                    
            for(i=1;i<=n;i++)
                    
            {
                        
            for(j=0;j<=c;j++)
                            printf(
            "%d ",m[i][j]);
                        printf(
            "\n");
                    }

                    
                    printf(
            "方案如下:\n");
                    
            for(i=1;i<=n;i++)
                        printf(
            "%d ",x[i]);
                    printf(
            "\n");
                }

                
            return 0;
            }

            運行結果如下:

                
                           第二種遞歸思路下的代碼和運行過程我就不寫,就初始化和遞歸次序不同??!
                           我一個同學經常跟我說,以后自己有孩子,一個賺了1000給我花100,一個賺了10000給我花200,我還是跟著賺1000的吧?。∑鋵崋栴}不在別人,而在自己,努力就成?。。∥沂芤娣藴\。。。
            posted on 2010-09-11 16:32 jince 閱讀(1853) 評論(0)  編輯 收藏 引用 所屬分類: 算法設計與分析
            哈哈哈哈哈哈
            2021国内久久精品| 久久久精品人妻无码专区不卡| 亚洲精品美女久久久久99小说| 日韩中文久久| 久久婷婷五月综合成人D啪| 一本一道久久综合狠狠老 | 久久香蕉国产线看观看精品yw| 亚洲另类欧美综合久久图片区| 欧美久久综合性欧美| 久久久久久精品无码人妻| 精品综合久久久久久97| 久久久久女教师免费一区| 无码人妻少妇久久中文字幕蜜桃| 国产精品日韩深夜福利久久| 久久最近最新中文字幕大全| 亚洲综合精品香蕉久久网| 狠狠色狠狠色综合久久| 国产色综合久久无码有码| 久久人人爽人人爽人人片AV麻烦| 久久丝袜精品中文字幕| 青青草原综合久久大伊人| 欧美黑人激情性久久| 久久国产香蕉视频| 丁香五月网久久综合| 久久久久高潮综合影院| 国产亚州精品女人久久久久久 | 久久久久亚洲AV无码麻豆| 国内精品久久久久久久影视麻豆| 精品熟女少妇a∨免费久久| 亚洲精品久久久www| 狠狠精品干练久久久无码中文字幕| 久久综合九色综合网站| 亚洲国产另类久久久精品| 2020国产成人久久精品| 久久久久综合国产欧美一区二区| 曰曰摸天天摸人人看久久久| 国产精品久久精品| 潮喷大喷水系列无码久久精品| 亚洲中文久久精品无码| 一本久久a久久精品vr综合| 久久九九兔免费精品6|