01背包问题 java

01背包问题

编辑

基本概念

01背包是 背包问题中最简单的问题。01背包的约束条件是给定几种物品，每种物品有且只有一个，并且有权值和体积两个属性。在01背包问题中，因为每种物品只有一个，对于每个物品只需要考虑选与不选两种情况。如果不选择将其放入背包中，则不需要处理。如果选择将其放入背包中，由于不清楚之前放入的物品占据了多大的空间，需要枚举将这个物品放入背包后可能占据背包空间的所有情况。

问题雏形

01背包题目的雏形是： 有N件物品和一个容量为V的背包。第i件物品的重量是weight[i]，价值是value[i]。求解将哪些物品装入背包可使价值总和最大。 从这个题目中可以看出，01背包的特点就是：每种物品仅有一件，可以选择放或不放。

01背包的状态转换方程 f[i,j] = Max{ f[i-1,j-Wi]+Vi( j >= Wi ),  f[i-1,j] }

import java.util.Scanner; public class beibao01 { public static void main(String[] args) { int n,m,total; Scanner in=new Scanner(System.in); n=in.nextInt();//物品数 total=in.nextInt();//最大容量 int weight[]=new int[n+1];//物品重量 int value[]=new int[n+1];//物品价值 int f[][]=new int[n+1][total+1]; for(int i=1;i<=n;i++){ weight[i]=in.nextInt(); value[i]=in.nextInt(); } for(int i=1;i<=n;i++){//枚举物品数 for(int j=1;j<=total;j++){//枚举重量 f[i][j]=f[i-1][j]; if(weight[i]<=j) {//f[i][j]前i件物品放到一个容量为v的背包中可以获得最大价值 f[i][j]=Math.max(f[i-1][j], f[i-1][j-weight[i]]+value[i]); //将i-1件容量为j时的价值 和 //i-1件容量为j-weight[i]时 加入第 //i件后的价值比较， } } }for(int i=1;i<=n;i++) System.out.println(f[i][total]);//依次输出i件物品最大容量的价值 } }