01背包问题用DP（动态规划实现）

背包容量int c = 10

物品个数int n = 5

物品重量w[] = {0, 2, 2, 6, 5, 4}

物品价值v[] = {0, 6, 3, 5, 4, 6}

结果存放result[][] = new int[n + 1][c + 1]//result[i][j]的意义，i个物品中放到容量为j中最大价值（放或者不放两种情况）

递推关系result[i][j] = max{result[i - 1][j], result[i - 1][j - w[i]] + v[j]}

1 package com.gxf.bag; 2  3 /** 4  * 背包问题 5  * @author Administrator 6  * 7  */ 8 public class Bag { 9     int n = 5;//物品个数10     int w[] = {0, 2, 2, 6, 5, 4};//物体重量11     int v[] = {0, 6, 3, 5, 4, 6};//物体价值12     int c = 10;//背包容量13     int result[][] = new int[n + 1][c + 1];//注意这里的意义，这里应该可以压缩，最后结果存放在result[n][c]中14     15     public int getMaxValue(){
   //result[i][j] 第i个物体放到容量为j的背包中最大价值16         17         for(int i = 0; i <= n; i++){18             for(int j = 0; j <= c; j++){19                 if(0 == i){20                     result[i][j] = 0;//没有物品放入,价值为021                 }22                 else if(j > 0 && j >= w[i]){23                     result[i][j] = Math.max(result[i - 1][j], result[i - 1][j - w[i]] + v[i]);24                 }25             }26         }27         28         return result[n][c];29     }30     /**31      * 打印数组result32      */33     public void showResult(){34         for(int i = 0; i <= n; i++){35             for(int j = 0; j <= c; j++){36                 System.out.print(result[i][j] + "\t");37             }38             System.out.println();39         }40     }41     42     /**43      * 测试44      * @param args45      */46     public static void main(String args[]){47         Bag bag = new Bag();48         System.out.println(bag.getMaxValue());49         //bag.showResult();50     }51 }