免费视频淫片aa毛片_日韩高清在线亚洲专区vr_日韩大片免费观看视频播放_亚洲欧美国产精品完整版

打開APP
userphoto
未登錄

開通VIP，暢享免費(fèi)電子書等14項超值服

開通VIP

首頁

好書

留言交流

下載APP

聯(lián)系客服
算法設(shè)計與分析 3.9 0-1背包問題
  1. /**********************************************************
  2. *        3.9        0-1背包問題
  3. *
  4. *        問題描述：
  5. *                給定n種物品和一背包。物品 i 的重量是 w[i] ，其價值為
  6. *        v[i] ，背包的容量為 c 。問:應(yīng)該如何選擇裝入背包中的物品，
  7. *        使得裝入背包中物品的總價值最大？
  8. *                
  9. *                在選擇裝入背包中的物品時，對每種物品 i 只有兩種選擇，
  10. *        即裝入或不裝入背包。不能將物品 i 裝入背包多次，也不能只
  11. *        裝入部分的物品 i 。因此，該問題稱為　0-1　背包問題。
  12. *
  13. *                此問題的形式化描述為，給定 c > 0, w[i] > 0, v[i] > 0
  14. *        1 <= i <= n ,要求找出 n 元 0-1 向量 x[1 .. n], 其中x[i]
  15. *        等于0或1,使得對 w[i] * x[i] 求和小于等于 c ，并且 v[i] * 
  16. *        x[i]達(dá)到最大。因此，0-1背包問題是一個特殊的整數(shù)規(guī)劃問題。
  17. *
  18. ***********************************************************/
  19.  
  20.  
  21. public class BagZeroOne {
  22.  
  23.         /**********************************************************************
  24.         *                        動態(tài)規(guī)劃解 (Dynamic Programming)
  25.         *        
  26.         *        @param v        in        the 物品價值數(shù)組
  27.         *        @param w        in        the 物品重量數(shù)組
  28.         *        @param c        in        the 背包的容量
  29.         *        @param m        out        the 最優(yōu)值數(shù)組，m[i][j]即背包容量為j,可選物品為 i, i + 1, ... , n 時0-1背包問題的最優(yōu)值
  30.         *        
  31.         *        由于0-1背包問題的最優(yōu)子結(jié)構(gòu)性質(zhì)，可以建立計算m[i][j]的遞歸式如下：
  32.         *                         / max{m[i + 1][j]), m[i + 1][j - w[i]] + v[i]}                j >= w[i]        
  33.         *        m[i][j]       /
  34.         *                        \
  35.         *                          \ m[i + 1][j]                                                         0 <= j < w[i]
  36.         *
  37.         *                        / v[n]                                                                    j >= w[n]
  38.         *        m[n][j]    /
  39.         *                      \
  40.         *                        \ 0                                                                        0 <= j < w[n]
  41.         *
  42.         **********************************************************************/
  43.     public static void knapsack(int[] v, int[] w, int c, int[][] m) {
  44.                 int n = v.length - 1;
  45.                 int jMax = Math.min(w[n] - 1, c);
  46.                 for (int j = 0; j <= jMax; j++) {
  47.                     m[n][j] = 0;
  48.                 }
  49.                 for (int j = w[n]; j <= c; j++) {
  50.                     m[n][j] = v[n];
  51.                 }
  52.                 for (int i = n - 1; i > 0; i--) {
  53.                     jMax = Math.min(w[i] - 1, c);
  54.                         for (int j = 0; j <= jMax; j++) {
  55.                             m[i][j] = m[i + 1][j];
  56.                         }
  57.                         for (int j = w[i]; j <= c; j++) {
  58.                             m[i][j] = Math.max(m[i + 1][j], m[i + 1][j - w[i]] + v[i]);
  59.                         }
  60.                 }
  61.                 /*
  62.                 m[1][c] = m[2][c];
  63.                 if (c >= w[1]) {
  64.                     m[1][c] = Math.max(m[1][c], m[2][c - w[1]] + v[1]);
  65.                 }
  66.                 */
  67.         }
  68.  
  69.         /**
  70.         *        @param        m        in        the 最優(yōu)值數(shù)組
  71.         *        @param        w        in        the 重量數(shù)組         
  72.         *        @param        c        in        the 背包容量
  73.         *        @param        x        out        the 物品選擇數(shù)組 if x[i] == 1 則選物品 i, 否則不選
  74.         **/
  75.         public static void trackback(int[][] m, int[] w, int c, int[] x) {
  76.                 int n = w.length - 1;
  77.                 for (int i = 1; i < n; i++) {
  78.                     if (m[i][c] == m[i + 1][c]) {
  79.                         x[i] = 0;                //不選物品 i 
  80.                     } else {
  81.                         x[i] = 1;                //選擇物品 i
  82.                                 c -= w[i];                //剩余容量
  83.                     }
  84.                 }
  85.                 x[n] = (m[n][c] > 0)? 1: 0;
  86.         }
  87.  
  88.         public static void testDynamicProgramming() {
  89.                 System.out.print("1. --- testDynamicProgramming      ---> ");
  90.                 //輸入
  91.                 int c = 7;
  92.                 int[] w = {0, 5, 3, 2, 1};
  93.                 int[] v = {0, 4, 4, 3, 1};
  94.                 
  95.                 //應(yīng)該的輸出
  96.                 int expectedVMax = 8;
  97.                 int[] expectedX = {0, 0, 1, 1, 1};
  98.                 
  99.                 //程序運(yùn)行時變量
  100.                 int[][] m = new int[w.length][c + 1];
  101.                 int[] x = new int[w.length];
  102.  
  103.  
  104.                 knapsack(v, w, c, m);
  105.                 trackback(m, w, c, x);
  106.                 
  107.                 if (m[1][c] == expectedVMax && java.util.Arrays.equals(x, expectedX)) {
  108.                     System.out.println("Test success!");
  109.                 } else {
  110.                     System.out.println("Test fail!");
  111.                 }
  112.         }
  113.  
  114.         /******************************************************************************
  115.         *                        暴力解　(Brutal Force)
  116.         *
  117.         *        物品 i 的重量 w[i], 價值 v[i]
  118.         *        
  119.         *        遞歸算法
  120.         *                try (物品 i, 當(dāng)前選擇已經(jīng)達(dá)到的重量之和 tw, 本方案可能達(dá)到的總價值 tv) 
  121.         *                {
  122.         *                        //考慮物品 i 包含在當(dāng)前方案的可能性
  123.         *                        if (包含物品 i 是可接受的)
  124.         *                        {
  125.         *                                將物品 i 包含在當(dāng)前方案中；
  126.         *                                if (i < n - 1) 
  127.         *                                        try(i + 1, tw + w[i], tv);
  128.         *                                else        //又是一個完整方案，因它比前面的方案要好，以它作為最佳方案
  129.         *                                        以當(dāng)前方案作為臨時最佳方案保存
  130.         *                                恢復(fù)物品 i 不包含在內(nèi)的狀態(tài)
  131.         *                        }
  132.         *                        //考慮物品 i 不包含在當(dāng)前方案中的可能性
  133.         *                        if (不包含物品 i 僅是可考慮的)
  134.         *                        {
  135.         *                                if (i < n - 1)
  136.         *                                        try(i + 1, tw, tv - v[i]);
  137.         *                                else        //又是一個完整方案，因它比前面的方案要好，以它作為最佳方案
  138.         *                                        以當(dāng)前方案作為臨時最佳方案保存
  139.         *                        }
  140.         *                }
  141.         ******************************************************************************/
  142.  
  143.         private static int[] w;                        //重量
  144.         private static int[] v;                        //價值
  145.         private static int[] x;                        //最優(yōu)解
  146.         private static int[] opt;                //有效解
  147.         private static int c;                        //背包容量
  148.         private static int maxv;                //最優(yōu)值
  149.  
  150.         public static void find(int i, int tw, int tv) {
  151.                 //考慮物品 i 包含在當(dāng)前方案中的可能性
  152.                 if (tw + w[i] <= c) {        //包含物品 i 是可以接受的
  153.                     opt[i] = 1;
  154.                         if (i < w.length - 1) {
  155.                             find(i + 1, tw + w[i], tv);
  156.                         } else {                        //又是一個完整方案，因它比前面的方案好，以它作為最佳方案
  157.                             for (int j = 0; j < x.length; j++) {
  158.                                 x[j] = opt[j];
  159.                             }
  160.                                 maxv = tv;
  161.                         }
  162.                         opt[i] = 0;
  163.                 }
  164.                 //考慮物品 i 不包含在當(dāng)前方案中的可能性
  165.                 if (tv - v[i] > maxv) {        //不包含物品 i 是可以考慮的
  166.                     if (i < w.length - 1) {
  167.                         find(i + 1, tw, tv - v[i]);
  168.                     } else { //又是一個完整方案，因它比前面的方案好，以它作為最佳方案
  169.                         for (int j = 0; j < x.length; j++) {
  170.                             x[j] = opt[j];
  171.                         }
  172.                                 maxv = tv - v[i];
  173.                     }
  174.                 }
  175.         }
  176.  
  177.         public static void testBrutalForceRecursive() {
  178.                 System.out.print("2. --- testBrutalForceRecursive    ---> ");
  179.                 int[] expectedX = {0, 1, 1, 1};
  180.                 int        expectedMaxV = 8;
  181.  
  182.                 w = new int[] {5, 3, 2, 1};
  183.                 v = new int[] {4, 4, 3, 1};
  184.                 x = new int[w.length];
  185.                 opt = new int[w.length];
  186.                 c = 7;
  187.                 int tv = 0;
  188.                 for (int i : v) {
  189.                         tv += i;    
  190.                 }
  191.  
  192.                 find(0, 0, tv);                
  193. //                System.out.println("maxv = " + maxv);
  194. //                System.out.println("x = " + java.util.Arrays.toString(x));
  195.                 if (maxv == expectedMaxV && java.util.Arrays.equals(x, expectedX)) {
  196.                     System.out.println("Test success!");
  197.                 } else {
  198.                     System.out.println("Test fail!");
  199.                 }
  200.         }
  201.  
  202.         /****************************************************************
  203.         *                暴力解 (Brutal Force)
  204.         *        
  205.         *        非遞歸算法
  206.         *
  207.         *
  208.         *****************************************************************/
  209.  
  210.         //當(dāng)前候選解中各物品的考慮和選擇狀態(tài)，以及置該物品候選解的狀態(tài)
  211.         private static int[] flag;                                //物品的考慮狀態(tài)：0.不選;1.將被考慮;2.曾被選中
  212.         private static int[] twe;                                //已經(jīng)達(dá)到的總重量
  213.         private static int[] tve;                                //期望的總價值
  214.  
  215.         private static int maxw;                                //背包容量
  216.         private static int[] cop;                                //臨時最佳解的物品選擇方案，當(dāng)cop[i] 為 1 時，物品 i 在解中
  217.  
  218.         //將考慮物品 i 
  219.         private static void next(int i, int tw, int tv) {
  220.                 flag[i] = 1;
  221.                 twe[i] = tw;
  222.                 tve[i] = tv;
  223.         }
  224.         public static int find(int[] w, int[] v, int n) {
  225.                 int i, k, f;
  226.                 int maxv, tw, tv, totv = 0;
  227.                 maxv = 0;
  228.                 for (int value : v) {
  229.                     totv += value;
  230.                 }
  231.                 next(0, 0, totv);
  232.                 i = 0;
  233.  
  234.                 while (i >= 0) {
  235.                     f = flag[i];
  236.                         tw = twe[i];
  237.                         tv = tve[i];
  238.                         switch (f) {
  239.                                 case 0:                                                                                                        //回退
  240.                                         i--;
  241.                                         break;
  242.  
  243.                             case 1:                                                                                                        //考慮被選中
  244.                                 flag[i]++;
  245.                                         if (tw + w[i] <= maxw) {                                                        //選中可行嗎？
  246.                                             if (i < n - 1) {
  247.                                                 next(i + 1, tw + w[i], tv);
  248.                                                         i++;
  249.                                             } else {
  250.                                                 maxv = tv;
  251.                                                         for (k = 0; k < n; k++) {
  252.                                                             cop[k] = ((flag[k] != 0)? 1 : 0);
  253.                                                         }
  254.                                             }
  255.                                         }
  256.                                 break;
  257.  
  258.                             default:                                                                                                //flag等于2
  259.                                 flag[i] = 0;
  260.                                         if (tv - v[i] > maxv) {                                                                //不選物品 i 可行嗎？
  261.                                             if (i < n - 1) {
  262.                                                 next(i + 1, tw, tv - v[i]);
  263.                                                         i++;
  264.                                             } else {
  265.                                                 maxv = tv - v[i];
  266.                                                         for (k = 0; k < n; k++) {
  267.                                                             cop[k] = ((flag[k] != 0)? 1 : 0);                                                            
  268.                                                         }
  269.                                             }
  270.                                         }
  271.                                 break;
  272.                         }
  273.                 }
  274.                 return maxv;
  275.         }
  276.  
  277.         public static void testBrutalForceNotRecursive() {
  278.                 System.out.print("3. --- testBrutalForceNotRecursive ---> ");
  279.                 int[] expectedX = {0, 1, 1, 1};
  280.                 int expectedMaxV = 8;
  281.                 
  282.                 int[] w = new int[] {5, 3, 2, 1};
  283.                 int[] v = new int[] {4, 4, 3, 1};
  284.                 int n = w.length;
  285.                 
  286.                 cop = new int[n];
  287.  
  288.                 flag = new int[n];
  289.                 twe = new int[n];
  290.                 tve = new int[n];
  291.  
  292.                 maxw = 7;
  293.  
  294.                 int maxv = find(w, v, n);                
  295. //                System.out.println("maxv = " + maxv);
  296. //                System.out.println("x = " + java.util.Arrays.toString(x));
  297.                 if (maxv == expectedMaxV && java.util.Arrays.equals(cop, expectedX)) {
  298.                     System.out.println("Test success!");
  299.                 } else {
  300.                     System.out.println("Test fail!");
  301.                 }
  302.  
  303.         }
  304.  
  305.         public static void main(String[] args) {
  306.                 testDynamicProgramming();
  307.                 testBrutalForceRecursive();
  308.                 testBrutalForceNotRecursive();
  309.         }
  310. }
本站僅提供存儲服務(wù)，所有內(nèi)容均由用戶發(fā)布，如發(fā)現(xiàn)有害或侵權(quán)內(nèi)容，請點(diǎn)擊舉報。
打開APP，閱讀全文并永久保存 查看更多類似文章
猜你喜歡
類似文章
五大常見算法策略之——動態(tài)規(guī)劃策略（Dynamic Programming）
0-1背包
面試中常見遞歸題目 Java版
Java面試中經(jīng)常問到的算法題 - - JavaEye技術(shù)網(wǎng)站
七大常見排序算法總結(jié)
經(jīng)典算法
更多類似文章 >>
生活服務(wù)
分享 收藏 導(dǎo)長圖 關(guān)注 下載文章
綁定賬號成功
后續(xù)可登錄賬號暢享VIP特權(quán)！
如果VIP功能使用有故障，
可點(diǎn)擊這里聯(lián)系客服！

聯(lián)系客服