2022-08-12:方案1 : {7, 10}; xxxx : {a , b}; 1 2 3 4; FunnyGoal = 100; OffenseGoal = 130。 找到一个最少方案数,让FunnyGoal、OffenseGoal,都大于等于。 定义如下尝试过程: 贴纸数组stickers, stickers[i][0] : i号贴纸的Funny值, stickers[i][1] : i号贴纸的Offense值。 index…所有的贴纸,随便选择。index之前的贴纸不能选择, 在让restFunny和restOffense都小于等于0的要求下,返回最少的贴纸数量。 来自弗吉尼亚理工大学(VT),算法考试卷。

答案2022-08-12:

递归,从左往右,要i还是不要i。 动态规划。

代码用rust编写。代码如下:

fn main() {

let mut stickers: Vec> =

vec![vec![1, 5], vec![2, 4], vec![3, 3], vec![4, 2], vec![5, 1]];

let ans1 = min_stickers1(&mut stickers, 3, 5);

let ans2 = min_stickers2(&mut stickers, 3, 5);

let ans3 = min_stickers3(&mut stickers, 3, 5);

println!("ans1 = {}", ans1);

println!("ans2 = {}", ans2);

println!("ans3 = {}", ans3);

}

fn min_stickers1(stickers: &mut Vec>, funny_goal: i32, offense_goal: i32) -> i32 {

return process1(stickers, 0, funny_goal, offense_goal);

}

const MAX_VALUE: i32 = 1 << 31 - 1;

fn process1(stickers: &mut Vec>, index: i32, rest_funny: i32, rest_offense: i32) -> i32 {

if rest_funny <= 0 && rest_offense <= 0 {

return 0;

}

if index == stickers.len() as i32 {

return MAX_VALUE;

}

// 不选当前的贴纸

let p1 = process1(stickers, index + 1, rest_funny, rest_offense);

// 选当前贴纸

let mut p2 = MAX_VALUE;

let next2 = process1(

stickers,

index + 1,

get_max(0, rest_funny - stickers[index as usize][0]),

get_max(0, rest_offense - stickers[index as usize][1]),

);

if next2 != MAX_VALUE {

p2 = next2 + 1;

}

return get_min(p1, p2);

}

fn get_max(a: T, b: T) -> T {

if a > b {

a

} else {

b

}

}

fn get_min(a: T, b: T) -> T {

if a < b {

a

} else {

b

}

}

// 改动态规划

fn min_stickers2(stickers: &mut Vec>, funny_goal: i32, offense_goal: i32) -> i32 {

let mut dp: Vec>> = vec![];

for i in 0..stickers.len() as i32 {

dp.push(vec![]);

for j in 0..funny_goal + 1 {

dp[i as usize].push(vec![]);

for _ in 0..offense_goal + 1 {

dp[i as usize][j as usize].push(0);

}

}

}

for i in 0..stickers.len() as i32 {

for j in 0..=funny_goal {

for k in 0..=offense_goal {

dp[i as usize][j as usize][k as usize] = -1;

}

}

}

return process2(stickers, 0, funny_goal, offense_goal, &mut dp);

}

fn process2(

stickers: &mut Vec>,

index: i32,

rest_funny: i32,

rest_offense: i32,

dp: &mut Vec>>,

) -> i32 {

if rest_funny <= 0 && rest_offense <= 0 {

return 0;

}

if index == stickers.len() as i32 {

return MAX_VALUE;

}

if dp[index as usize][rest_funny as usize][rest_offense as usize] != -1 {

return dp[index as usize][rest_funny as usize][rest_offense as usize];

}

// 不选当前的贴纸

let p1 = process2(stickers, index + 1, rest_funny, rest_offense, dp);

// 选当前贴纸

let mut p2 = MAX_VALUE;

let next2 = process2(

stickers,

index + 1,

get_max(0, rest_funny - stickers[index as usize][0]),

get_max(0, rest_offense - stickers[index as usize][1]),

dp,

);

if next2 != MAX_VALUE {

p2 = next2 + 1;

}

let ans = get_min(p1, p2);

dp[index as usize][rest_funny as usize][rest_offense as usize] = ans;

return ans;

}

// 严格位置依赖的动态规划

fn min_stickers3(stickers: &mut Vec>, funny_goal: i32, offense_goal: i32) -> i32 {

let n = stickers.len() as i32;

let mut dp: Vec>> = vec![];

for i in 0..n + 1 {

dp.push(vec![]);

for j in 0..funny_goal + 1 {

dp[i as usize].push(vec![]);

for _ in 0..offense_goal + 1 {

dp[i as usize][j as usize].push(0);

}

}

}

for f in 0..=funny_goal {

for o in 0..=offense_goal {

if f != 0 || o != 0 {

dp[n as usize][f as usize][o as usize] = MAX_VALUE;

}

}

}

let mut i = n - 1;

while i >= 0 {

for f in 0..=funny_goal {

for o in 0..=offense_goal {

if f != 0 || o != 0 {

let p1 = dp[(i + 1) as usize][f as usize][o as usize];

let mut p2 = MAX_VALUE;

let next2 = dp[(i + 1) as usize]

[get_max(0, f - stickers[i as usize][0]) as usize]

[get_max(0, o - stickers[i as usize][1]) as usize];

if next2 != MAX_VALUE {

p2 = next2 + 1;

}

dp[i as usize][f as usize][o as usize] = get_min(p1, p2);

}

}

}

i -= 1;

}

return dp[0][funny_goal as usize][offense_goal as usize];

}

执行结果如下:

左神java代码

参考阅读

评论可见,请评论后查看内容,谢谢!!!评论后请刷新页面。