本文共 2049 字，大约阅读时间需要 6 分钟。

思路过程：

题目的关键是每个物品只有一个，不能拿物品的一半或者一些，面对每个物品，我们只有选择拿取或者不拿两种选择，不能选择拿取某物品的一部分，也不能装入同一物品多次。

解决的办法：声明一个大小为m[n][c]的二维数组，m[i][j]表示面对第i件物品，且背包容量为j时所能获取的最大价值，那么我们可以很容易分析得出m[i][j]的计算方法，

（1）.当j<w[i]情况，这时候背包容量不足以放下第i件物品，只能选择不拿m[i][j]=m[i-1][j]。（用自己话来说，就是前一个背包装的物品继续装着，不把它拿出来）

（2）.当j>=w[i]情况，这是背包容量可以放下第i件物品，我们就要考虑拿这件物品是否能获取更大的价值？

如果拿取，m[i][j]=m[i-1][j-w[j]]+v[i]。这里的m[i-1][j-w[j]]指的就是考虑了i-1件物品(上一件物品)，背包容量为j-w[i]时的最大价值，也是相当于为第i件物品腾出了w[i]的空间。

如果不拿，m[i][j]=m[i-1][j]，同（1）

究竟是拿还是不拿，自然是比较这两种情况哪一种价值最大，就选哪一个啦。。bingo~~~~~~

由此可以得到状态转移方程：

if(j>=w[i])    m[i][j]=max(m[i-1][j],m[i-1][j-w[i]]+v[i]);else    m[i][j]=m[i-1][j];

使用动态规划算法求解题目的0-1背包问题：使用二维数组m[i][j]存储背包剩余容量为j，可选物品i、i+1、...、n时，0-1背包问题的最优解。

价值数组v={3，5，7}；

重量数组w={2，3，4}；

背包容量为C=5时对应的m[i][j]数组。

下面一段话重要~~

*****如m[3][4],在面对第三件物品，背包重量为4时，我们可以选择不拿，那么获得价值仅为第一件物品的价值5，如果拿，就要把第二件物品拿出来，放第三件物品，价值7，那我们当然是选择拿啦（有价值大的物品，肯定拿取价值大的啦，没可能价值小的吧~~）。m[3][4]=m[2][0]+7=7；依次类推啦，得到m[3][5]就是考虑所有物品，背包容量为C时的最大价值。

代码如下：

import java.util.Scanner;public class Main {	public static void main(String[] args) {		// TODO Auto-generated method stub		Scanner scanner = new Scanner(System.in);		int n = scanner.nextInt();		int m = scanner.nextInt();		int w[] = new int[n+1];		int v[] = new int[n+1];		for(int i=1;i<=n;i++){			w[i]=scanner.nextInt();			v[i]=scanner.nextInt();		}		int p=maxPrice(w,v,n,m);		System.out.println(p);	}	private static int maxPrice(int[] w, int[] v, int n, int m) {		//寻找最大价值		//w:物品重量数组;v:物品价值数组;n:物品数量;m：背包的最大体积		//dp[n][m]代表在前n个物品中任取若干个存入体积为m的背包中，形成的物品最大价值		int[][] dp = new int[n+1][m+1];		for(int i=1;i<=n;i++){			for(int j=1;j<=m;j++){				if(w[i]>j){					dp[i][j]=dp[i-1][j];				}else{					dp[i][j]=Math.max(dp[i-1][j], dp[i-1][j-w[i]]+v[i]);				}			}		}		return dp[n][m];	}}

总结 01-背包问题 （动态规划算法）

转载地址：http://iuwkf.baihongyu.com/