php实现0-1背包问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26



 php
function (){
    $a['w'] = [0, 2, 3, 4, 5, 9];
    $a['v'] = [0, 3, 4, 5, 8, 10];
    $b =array();
    $n = 6;
    $w = 21;
    for($i=0;$i < $n;$i++){
        for($j=0;$j < $w;$j++){
            $b[$i][$j] = 0;
        }
    }
    for($k = 1; $k < $n ;$k++){
        for($c = 1; $c < $w ;$c++){
            if($a['w'][$k] > $c){
                $b[$k][$c] = $b[$k-1][$c];
            }else{
                $value1 = $b[$k-1][$c-$a['w'][$k]] + $a['v'][$k]; 
                $value2 = $b[$k-1][$c]; // 不拿第k件物品
                $b[$k][$c] = max($value1,$value2);
            }
        }
    }
    print_r($b);
}
back();







 JAVA实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20



  class Main {
  public static void main(String[] args) {
      int[] w = { 0, 2, 3, 4, 5, 9 };
      int[] v = { 0, 3, 4, 5, 8, 10 };
      int N = 6, W = 21;
      int[][] b = new int[N][W];
      for (int k = 1; k < N; k++) {
          for (int c = 1; c < W; c++) {
              if (w[k] > c) {
                  b[k][c] = b[k - 1][c];
              } else {
                  int value1 = b[k - 1][c - w[k]] + v[k]; 
                  int value2 = b[k - 1][c]; // 不拿第k件物品
                  b[k][c] = Math.max(value1, value2);
              }
          }
      }
      System.out.println(b[5][20]);
  }
}








			
赞微海报分享