算法训练采果子

68 阅读 0 评论 45 点赞

我是靠谱客的博主缓慢手链，最近开发中收集的这篇文章主要介绍算法训练采果子，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

Lyl大牛今天心情不错，于是走到埃及郊外旅游(会不会碰到MMY?...PS:MMY的含义请自行理解)。他边走边向四周望望，发现周围有许多果树。这些树之间互相到达的时间Lyl是知道的（假定每两棵树之间都拥有独立的边可以到达）。他数出了这些果树上果子的个数，并且估了估每个的价格（真是个奇怪的人）。Lyl规定了一种采摘方案，就是对于第i棵树来说，它有a[i]个果子，且所有果子价值为s[i]，摘取时间为c[i](小时)。并且，当他摘了第i个树上的果子后，后面他所选择去摘的果树上的果子数必须大于第i棵树上的果子数目，说白了就是一个上升序列；并且每到一棵树，他都必须摘下该树上的所有果子。一开始，Lyl可以在任意一棵树，他只有m小时，那么，在他所拥有的限定时间内，他想知道，这样摘取的最大价值是多少？

输入格式

　　输入文件tree.in第一行2个数：n（表示这条路上的大树数），m（总共时间）
　　接下来第n+1行，每行三个数a[i],s[i],c[i] (第i+1行输入的为第i颗果树的信息)
　　且保证有1<=a[i]<=2^31-1;1<=s[1]+s[2]+…+s[n]<=2^31-1;s[i]>=0; 1<=c[i]<=100
　　接下来的n行，每行n个数，第i行第j个数表示从树i到树j的时间。（0<=T[I,j]<=100;）

输出格式

　　输出文件tree.out有且仅有一个数，即按这样方法摘取的最大价值。

样例输入

4 10
1 10 2
2 5 3
3 6 1
4 9 4
0 1 2 3
1 0 3 4
2 3 0 5
3 4 5 0

样例输出

21
（先摘第1棵树上的，再摘第2棵树上的，然后第3棵树上的）

数据规模和约定

　　对于60%的数据 ,1<=N<=60,1<=m<=100;
　　对于100%的数据 ,1<=N<=100, 1<=m<=1000.

import java.util.Scanner;
public class Main {
static Tree[] tree = new Tree[110];//树的相关信息
static int[][] Cross = new int[110][110];//Cross[i][j] 树i到树j所用的时间
static int n,m;
static int maxV=0;//最大价值
static int[][] Dp = new int[110][1010];//
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
//1.输入相关的数据
n = sc.nextInt();//树的个数
m = sc.nextInt();//可以采摘的总时间
tree[0] = new Tree(0,0,0,0);
for(int i=1;i<=n;i++){
tree[i] = new Tree();
tree[i].id = i;
tree[i].count = sc.nextInt();
tree[i].value = sc.nextInt();
tree[i].cost = sc.nextInt();
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
Cross[i][j] = sc.nextInt();
}
}
//2.按照果子数目递减的顺序，排列树(冒泡排序)
boolean flag;
for(int i=n;i>0;i--){
flag = false;
for(int j=1;j<i;j++){
if(tree[j].count<tree[j+1].count){
Tree temp = tree[j];
tree[j] = tree[j+1];
tree[j+1] = temp;
flag = true;
}
}
if(flag == false) break; //没有进行交换
}
//3.找出最大值
for(int i=1;i<=n;i++){
for(int j=0;j<i;j++){//此时j的果子数目>=i的果子数目
if(tree[i].count == tree[j].count) continue; //树i和树j的果子数目一样，跳过本次循环
int tval = tree[i].value;//树i的总价值
int tcost = tree[i].cost+Cross[tree[i].id][tree[j].id];//树i的总代价+从树i到树j的总代价
for(int o=m-tcost;o>=0;o--){//o:表示当前剩下可用的时间
Dp[i][o]=Math.max(Dp[i][o], Dp[j][o+tcost]+tval);
maxV = Math.max(maxV,Dp[i][o]);
}
}
}//for
//5.输出最大的价值
System.out.println(maxV);
}
}
//1.表示树的相关信息
class Tree{
int id;//树的编号
int count,value,cost;//果子数、该树的总价值、摘果子用的时间
public Tree(){
}
public Tree(int id, int count, int value, int cost) {
super();
this.id = id;
this.count = count;
this.value = value;
this.cost = cost;
}
}