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

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

写在前面

很久以前在有道云笔记上写的笔记,打算放弃它了,将笔记迁移到这里来。文章可能还有很多不足,请大家谅解,欢迎大佬提意见。

本文使用到的东西

  1. java
  2. ecplipse

1.正文

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]+"。");
			}
		}
	}
}

2.总结

很久以前在有道云笔记上写的笔记,打算放弃它了,将笔记迁移到这里来。有不清楚的地方欢迎评论留言,看到的我都会回复的。本文到此结束,有什么不足的地方请大家不吝指正。

---------本文结束感谢您的阅读---------

评论

 热烈欢迎各位大佬专家莅临玖涯博客指导检查!

 交换友链的朋友请前往友情链接

 热烈欢迎各位大佬专家莅临玖涯博客指导检查!

 交换友链的朋友请前往友情链接

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×