动态规划算法的应用方案：背包问题
条件：
目标是1 )安装的背包总价值最大，且重量2 )安装的物品不重复
算法介绍：
1 )动态规划的核心思想)把大问题分成小问题解决，一步一步获得最优解的处理方法
2 )算法与分治算法相似，其基本思想也是将有解的问题分解成几个小问题，首先求出子问题，然后通过这些子问题的解得到原问题的解。
3 )与分治法不同，适用于通过动态规划求解的问题，分解得到的子问题往往不是相互独立的。 (即，下一阶段的解是基于前一阶段的解进一步求解)
4 )动态计划通过填写表格逐步进行，可以得到最优解。 背包问题01 01动态解决背包的计划：即一件物品最多放一个
public class demon1{ publicstaticvoidmain (string [ ] args ) int [ ] w={ 1，4，3 }； //物品的重量int [ ] val={ 1500，3000，2000 }； //物品的价值int m=4； //背包容量int n=val.length； //项目数量//二维阵列的创建//v[i][j]是容量为j的背包可以放在前I个项目中的最大价值int[][] v=new int[n 1][m 1]； //记录商品状况的int[][] path=new int[n 1][m 1]；//初始化第1行和第1列，输入for(intI=0； iv.length； I ) ) v(I ) )0)=0； //第一列为0}for(intI=0； iv[0].length； I ) ) v(0) ) I )=0； //将第一行设置为0}for(intI=1； iv.length； I ) for(intj=1； jv[0].length； j ) (/官方if ) w[I-1]j ) {v[i][j]=v[i-1][j]； (else )//公式应调整//v[I][j]=math.max ) v[I-1][j]、val[i-1] v[i-1][j-w[i-1]] ) //v[I][j]=math.max(v[I-1][j]、val[i-1] v[i-1][j-w[i-1]] )； //记录商品状况的if (v [ I-1 ] [ j ] val [ I-1 ] v [ I-1 ] [ j-w [ I-1 ] ] ) v[I][j]=val[I-1]v[I-1] ) }else {v[i][j]=v[i-1][j]； }}}}//当前状况for(intI=0； iv.length； I ) for(intj=0； jv[i].length； j ) (system.out.print ) v[I][j] ' )； }System.out.println (； //输出最后放入的商品//path//for (inti=0； ipath.length； I )//for(intj=0； jpath[i].length； j ) )/if(path[I](j )==1) {//System.out.printf )，第d个商品是背包(n )、I )； //////(intI=path.length-1； //行的最大下标int j=path[0].length-1； //列的最大下标while(I0j0) if ) path[I][j]==1) ) {System.out.printf )第d个商品是背包(n (，I )； j-=w[i-1]； (I----)； }}输出结果：