贪心算法获得最高分
Greedy algorithm to get highest score obtainable
我有一个考试，最高分是 55 分，时间限制是 50 分钟。我需要在 R 中设计一个贪心算法，以最大化在分配时间内可获得的点数。
假设：
-100% 正确尝试的问题
-一旦问题开始，就必须完成
我真的不知道该怎么做。
> table[order(table$Points_per_min, decreasing = T),]
Question Total_Points Time_needed Points_per_min
6 Q6 5 3 1.6666667
5 Q5 5 4 1.2500000
4 Q4 14 12 1.1666667
7 Q7 10 10 1.0000000
8 Q8 5 5 1.0000000
1 Q1 21 24 0.8750000
9 Q9 5 6 0.8333333
2 Q2 5 7 0.7142857
3 Q3 10 15 0.6666667
我想根据手算，我应该得到49个最高点数和47分钟的使用时间。我可能是错的。谢谢！
您可以将其设置为线性优化问题。您正在尝试根据时间限制最大化点数。此外，每个决策变量都应该是二元的，因为您不能两次回答同一个问题。
lpSolveAPI 是设置这些问题的 R 包。老实说，我发现语法有点密集，但非常强大。我能够找到一个 50 分的解决方案，它需要全部 50 分钟。 FWIW，我在 Excel 的 Solver() 中找到了相同的解决方案，在我看来这更直观一些。
完整的解决方案如下，但这是我们设置的模型的表示（这是设置模型后 write.lp() 的输出：
/* Objective function */
max: +21 Q1 +5 Q2 +10 Q3 +14 Q4 +5 Q5 +5 Q6 +10 Q7 +5 Q8 +5 Q9;
/* Constraints */
Time_Constraint: +24 Q1 +7 Q2 +15 Q3 +12 Q4 +4 Q5 +3 Q6 +10 Q7 +5 Q8 +6 Q9 <= 50;
/* Variable bounds */
Q1 <= 1;
Q2 <= 1;
Q3 <= 1;
Q4 <= 1;
Q5 <= 1;
Q6 <= 1;
Q7 <= 1;
Q8 <= 1;
Q9 <= 1;
/* Integer definitions */
int Q1,Q2,Q3,Q4,Q5,Q6,Q7,Q8,Q9;
library(lpSolveAPI)
library(data.table)
#Define questions, points, and time requirements
dt <- data.table(questions = paste0("Q", 1:9), points = c(21,5,10,14,5,5,10,5,5), time = c(24,7,15,12,4,3,10,5,6))
#make lp object with one contrasint and 9 decision variables
lprec <- make.lp(1,9)
#make sure we're maximizing, not minimizing
lp.control(lprec,sense='max')
#Set the names
dimnames(lprec) <- list("Time_Constraint", dt$questions)
#Set the objective function values, i.e. how many points we get
set.objfn(lprec, dt$points)
#assign the time taken to earn the points
set.row(lprec, 1, dt$time)
#what is the right hand side variable to 50
set.rhs(lprec, 50)
#make the variables binary
set.type(lprec, columns = 1:9, "binary")
#write this model out to see what it is
write.lp(lprec, filename = "model.lp", type = "lp")
#solve the model
solve(lprec)
#> [1] 0
#get the answers, i.e. which should be answered
answers <- get.variables(lprec)
#let's subset just the questions we should answer
dt[as.logical(answers), ]
#> questions points time
#> 1: Q1 21 24
#> 2: Q4 14 12
#> 3: Q5 5 4
#> 4: Q7 10 10
#and confirm that we don't go over 50 minutes
dt[as.logical(answers), .(points = sum(points), time_taken = sum(time))]
#> points time_taken
#> 1: 50 50
由 reprex package (v0.2.1)
于 2019-02-10 创建
Greedy 这里的方法是解决问题 每分钟得分的递减顺序.它不能确保为您提供@Chase 给出的最佳解决方案（最优），但已经足够好了。唯一的限制是不要超过时间限制。如果在处理过程中，您发现了违反此约束的问题，则跳过它。
# Initiate cumulative points
cum_points <- 0
# Initiate cumulative time used
cum_time <- 0
# Initiating Questions solved/finished in sequence/ index j
question_finished <- as.character()
j <- 1
# sort the data based on Points_per_min
library(dplyr)
df_sorted <- df %>% arrange(desc(Points_per_min))
# Checking question by question
for(i in 1:nrow(df_sorted)){
# only if cumulative time not exceeding time limit of 50 min, we solve a question
if(cum_time + df_sorted$Time_needed[i] <= 50){
cum_time <- cum_time + df_sorted$Time_needed[i]
cum_points <- cum_points + df_sorted$Total_Points[i]
# Storing the Solved/finished questions and incrementing j
Question_finished[j] <- as.character(df_sorted$Question[i])
j <- j + 1
}
}
Question_finished
#[1] "Q6" "Q5" "Q4" "Q7" "Q8" "Q9" "Q2"
cum_points
#[1] 49
cum_time
#[1] 47
使用的数据：
df <- read.table(text = "Question Total_Points Time_needed Points_per_min
6 Q6 5 3 1.6666667
5 Q5 5 4 1.2500000
4 Q4 14 12 1.1666667
7 Q7 10 10 1.0000000
8 Q8 5 5 1.0000000
1 Q1 21 24 0.8750000
9 Q9 5 6 0.8333333
2 Q2 5 7 0.7142857
3 Q3 10 15 0.6666667")
我有一个考试，最高分是 55 分，时间限制是 50 分钟。我需要在 R 中设计一个贪心算法，以最大化在分配时间内可获得的点数。
假设： -100% 正确尝试的问题 -一旦问题开始，就必须完成
我真的不知道该怎么做。
> table[order(table$Points_per_min, decreasing = T),]
Question Total_Points Time_needed Points_per_min
6 Q6 5 3 1.6666667
5 Q5 5 4 1.2500000
4 Q4 14 12 1.1666667
7 Q7 10 10 1.0000000
8 Q8 5 5 1.0000000
1 Q1 21 24 0.8750000
9 Q9 5 6 0.8333333
2 Q2 5 7 0.7142857
3 Q3 10 15 0.6666667
我想根据手算，我应该得到49个最高点数和47分钟的使用时间。我可能是错的。谢谢！
您可以将其设置为线性优化问题。您正在尝试根据时间限制最大化点数。此外，每个决策变量都应该是二元的，因为您不能两次回答同一个问题。
lpSolveAPI 是设置这些问题的 R 包。老实说，我发现语法有点密集，但非常强大。我能够找到一个 50 分的解决方案，它需要全部 50 分钟。 FWIW，我在 Excel 的 Solver() 中找到了相同的解决方案，在我看来这更直观一些。
完整的解决方案如下，但这是我们设置的模型的表示（这是设置模型后 write.lp() 的输出：
/* Objective function */
max: +21 Q1 +5 Q2 +10 Q3 +14 Q4 +5 Q5 +5 Q6 +10 Q7 +5 Q8 +5 Q9;
/* Constraints */
Time_Constraint: +24 Q1 +7 Q2 +15 Q3 +12 Q4 +4 Q5 +3 Q6 +10 Q7 +5 Q8 +6 Q9 <= 50;
/* Variable bounds */
Q1 <= 1;
Q2 <= 1;
Q3 <= 1;
Q4 <= 1;
Q5 <= 1;
Q6 <= 1;
Q7 <= 1;
Q8 <= 1;
Q9 <= 1;
/* Integer definitions */
int Q1,Q2,Q3,Q4,Q5,Q6,Q7,Q8,Q9;
library(lpSolveAPI)
library(data.table)
#Define questions, points, and time requirements
dt <- data.table(questions = paste0("Q", 1:9), points = c(21,5,10,14,5,5,10,5,5), time = c(24,7,15,12,4,3,10,5,6))
#make lp object with one contrasint and 9 decision variables
lprec <- make.lp(1,9)
#make sure we're maximizing, not minimizing
lp.control(lprec,sense='max')
#Set the names
dimnames(lprec) <- list("Time_Constraint", dt$questions)
#Set the objective function values, i.e. how many points we get
set.objfn(lprec, dt$points)
#assign the time taken to earn the points
set.row(lprec, 1, dt$time)
#what is the right hand side variable to 50
set.rhs(lprec, 50)
#make the variables binary
set.type(lprec, columns = 1:9, "binary")
#write this model out to see what it is
write.lp(lprec, filename = "model.lp", type = "lp")
#solve the model
solve(lprec)
#> [1] 0
#get the answers, i.e. which should be answered
answers <- get.variables(lprec)
#let's subset just the questions we should answer
dt[as.logical(answers), ]
#> questions points time
#> 1: Q1 21 24
#> 2: Q4 14 12
#> 3: Q5 5 4
#> 4: Q7 10 10
#and confirm that we don't go over 50 minutes
dt[as.logical(answers), .(points = sum(points), time_taken = sum(time))]
#> points time_taken
#> 1: 50 50
由 reprex package (v0.2.1)
于 2019-02-10 创建Greedy 这里的方法是解决问题 每分钟得分的递减顺序.它不能确保为您提供@Chase 给出的最佳解决方案（最优），但已经足够好了。唯一的限制是不要超过时间限制。如果在处理过程中，您发现了违反此约束的问题，则跳过它。
# Initiate cumulative points
cum_points <- 0
# Initiate cumulative time used
cum_time <- 0
# Initiating Questions solved/finished in sequence/ index j
question_finished <- as.character()
j <- 1
# sort the data based on Points_per_min
library(dplyr)
df_sorted <- df %>% arrange(desc(Points_per_min))
# Checking question by question
for(i in 1:nrow(df_sorted)){
# only if cumulative time not exceeding time limit of 50 min, we solve a question
if(cum_time + df_sorted$Time_needed[i] <= 50){
cum_time <- cum_time + df_sorted$Time_needed[i]
cum_points <- cum_points + df_sorted$Total_Points[i]
# Storing the Solved/finished questions and incrementing j
Question_finished[j] <- as.character(df_sorted$Question[i])
j <- j + 1
}
}
Question_finished
#[1] "Q6" "Q5" "Q4" "Q7" "Q8" "Q9" "Q2"
cum_points
#[1] 49
cum_time
#[1] 47
使用的数据：
df <- read.table(text = "Question Total_Points Time_needed Points_per_min
6 Q6 5 3 1.6666667
5 Q5 5 4 1.2500000
4 Q4 14 12 1.1666667
7 Q7 10 10 1.0000000
8 Q8 5 5 1.0000000
1 Q1 21 24 0.8750000
9 Q9 5 6 0.8333333
2 Q2 5 7 0.7142857
3 Q3 10 15 0.6666667")