动态规划-金矿问题、类似01背包

动态规划(dynamic programming)是运筹学的一个分支，是求解决策过程(decision process)最优化的数学方法。将复杂的问题分解成多个小问题，以空间换时间，将每个小问题的解保存下来，根据小问题的解来计算复杂的问题。本文提供了动态规划经典问题金矿问题的实现源码。

import java.util.*;
/**
 * 金矿挖掘问题，指定金矿需要矿工数量、金矿价值和矿工数
 * 目的：获取最大的价值，类似01背包
 * @author 殇雪话诀别
 *
 */
/*
 * 测试数据
5 17
8 11
4 5
9 13
3 12
7 10
 */
public class Main {
	
	public static void main(String[] args) {
		Scanner in=new Scanner(System.in);
		System.out.println("请输入金矿数量、矿工数量：");
		int n=in.nextInt();			//金矿数量
		int num=in.nextInt();		//矿工数
		int[][] jk=new int[2][n];	//用于存储金矿数量
		System.out.println("请输入需要矿工数、价值：");
		for(int i=0;i<n;i++) {
			jk[0][i]=in.nextInt();		//金矿重量
			jk[1][i]=in.nextInt();		//金矿价值
		}
		int[][] dt=new int[n+1][num+1];		//申请空间用于动态规划
		for(int i=1;i<=n;i++) {				//表示金矿数量为i是的情况
			for(int j=1;j<=num;j++) {		//表示当矿工数为j时的情况
				if(j<jk[0][i-1]) {			//矿工总数<当前金矿所需矿工数
					dt[i][j]=dt[i-1][j];	//矿工数不足以开采当前金矿，所以和没有该矿时的情况一样
				}else {
					/*
					 * 矿工数足以开采当前金矿，有两种情况，分别为：
					 * 开采该矿，再用开采后的矿工数去开采没有该矿时的情况
					 * 不开采该矿
					 */
					if(jk[1][i-1]+dt[i-1][j-jk[0][i-1]]>dt[i-1][j]) {
						dt[i][j]=jk[1][i-1]+dt[i-1][j-jk[0][i-1]];	//开采该矿，再用开采后的矿工数去开采没有该矿时的情况
					}else {
						dt[i][j]=dt[i-1][j];		//不开采该矿
					}
				}
			}
		}
		System.out.println("最多可挖掘"+dt[n][num]+"个金矿。");
		int s[]=new int[n];		//用于记录哪个金矿最终被开采了
		int w=num;
		for(int i=n;i>0;i--) {
			if(dt[i][w]!=dt[i-1][w]) {	//从后往前，如果当前价值和未使用这个金矿时的价值相等则表示未使用该金矿
				s[i-1]=1;
				w=w-jk[0][i-1];		//将矿工数减去当前矿需要的矿工数量
			}
		}
		for(int i=0;i<n;i++) {
			if(s[i]!=0) {
				System.out.println("第"+(i+1)+"个金矿，重量："+jk[0][i]+"，价值："+jk[1][i]+"。");
			}
		}
	}
}