蓝桥杯 PREV-8 买不到的数目

买不到的数目"/>

蓝桥杯 PREV-8 买不到的数目

蓝桥杯 PREV-8 买不到的数目

问题描述

小明开了一家糖果店。他别出心裁：把水果糖包成4颗一包和7颗一包的两种。糖果不能拆包卖。 小朋友来买糖的时候，他就用这两种包装来组合。当然有些糖果数目是无法组合出来的，比如要买 10 颗糖。 你可以用计算机测试一下，在这种包装情况下，最大不能买到的数量是17。大于17的任何数字都可以用4和7组合出来。 本题的要求就是在已知两个包装的数量时，求最大不能组合出的数字。
输入格式
两个正整数，表示每种包装中糖的颗数(都不多于1000)
输出格式
一个正整数，表示最大不能买到的糖数
样例输入
4 7
样例输出
17
样例输入
3 5
样例输出
7

思路解析

• 数论某定理：
  a 和 b 互 质 ， 则 二 者 的 最 大 不 可 组 合 数 为 ( a − 1 ) b − a , 不 可 组 合 数 的 数 目 为 ( a − 1 ) ( b − 1 ) 2 a和b互质，则二者的最大不可组合数为(a-1)b-a,不可组合数的数目为\frac{(a-1)(b-1)}{2} a和b互质，则二者的最大不可组合数为(a−1)b−a,不可组合数的数目为2(a−1)(b−1)​
  与这道题其实并不完全匹配，因题目中并没有给出互质的条件

• 完全背包问题

  该问题可以转换为一个完全背包问题。

  阅读所需基础：背包问题九讲前两讲

  对应关系如下：

  • 数–>背包
  • 数的大小–>背包的容量
  • 糖包–>物品
  • 糖包的糖数–>物品的价值、重量

  为了叙述方便，我们将

  • 输入的各糖包的糖数称为输入数
  • 将物品放入背包可获得的最大价值称为背包的最大价值。

  有以下结论：

  我们设定一个较大的值max_v（注意不能太大，否则造成内存溢出），假定该值大于最大不可组合数，从1遍历到max_v，将每一个值作为背包的容量计算出对应背包的最大价值，依次存储到数组 f [ v ] f[v] f[v]中。

  • 如果某一容量的背包的最大价值等于背包容量，即容量对应的数为输入数的组合数。

  • 如果某一容量的背包的最大价值小于背包容量，即容量对应的数不为输入数的组合数。

  得到数组 f [ v ] f[v] f[v]之后，从后往前遍历，找到第一个背包的最大价值小于背包容量的元素，此时的背包容量即所求的最大不可组合数。

代码如下：

#include<iostream>
#include<vector>
#include<algorithm>using namespace std;int main() {int n = 0, t, max_v = 100000;vector<int> c(1), w(1);while (cin >> t) {c.push_back(t);w.push_back(t);n++;}int f[100001] = { 0 };for (int i = 1; i <= n; i++) {for (int v = c[i]; v <= max_v; v++) {f[v] = max(f[v], f[v - c[i]] + w[i]);}}for (int i = max_v; i >= 0; i--) {if (f[i] < i) {cout << i;break;}}return 0;
}