2022-08-12：方案1 : {7, 10}； xxxx : {a , b}； 1 2 3 4； FunnyGoal = 100； OffenseGoal

原创

福大大架构师每日一题

发布于 2022-08-12 21:50:14

3370

发布于 2022-08-12 21:50:14

文章被收录于专栏：福大大架构师每日一题福大大架构师每日一题

2022-08-12：方案1 : {7, 10}；

xxxx : {a , b}；

1 2 3 4；

FunnyGoal = 100；

OffenseGoal = 130。

找到一个最少方案数，让FunnyGoal、OffenseGoal，都大于等于。

定义如下尝试过程：

贴纸数组stickers，

stickersi : i号贴纸的Funny值，

stickersi : i号贴纸的Offense值。

index....所有的贴纸，随便选择。index之前的贴纸不能选择，

在让restFunny和restOffense都小于等于0的要求下，返回最少的贴纸数量。

来自弗吉尼亚理工大学(VT)，算法考试卷。

答案2022-08-12：

递归，从左往右，要i还是不要i。

动态规划。

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

fn main() {
    let mut stickers: Vec<Vec<i32>> =
        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<Vec<i32>>, 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<Vec<i32>>, 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<T: Clone + Copy + std::cmp::PartialOrd>(a: T, b: T) -> T {
    if a > b {
        a
    } else {
        b
    }
}

fn get_min<T: Clone + Copy + std::cmp::PartialOrd>(a: T, b: T) -> T {
    if a < b {
        a
    } else {
        b
    }
}

// 改动态规划
fn min_stickers2(stickers: &mut Vec<Vec<i32>>, funny_goal: i32, offense_goal: i32) -> i32 {
    let mut dp: Vec<Vec<Vec<i32>>> = 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<Vec<i32>>,
    index: i32,
    rest_funny: i32,
    rest_offense: i32,
    dp: &mut Vec<Vec<Vec<i32>>>,
) -> 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<Vec<i32>>, funny_goal: i32, offense_goal: i32) -> i32 {
    let n = stickers.len() as i32;
    let mut dp: Vec<Vec<Vec<i32>>> = 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];
}

执行结果如下：