问题描述
小明开了一家糖果店。他别出心裁:把水果糖包成4颗一包和7颗一包的两种。糖果不能拆包卖。
小朋友来买糖的时候,他就用这两种包装来组合。当然有些糖果数目是无法组合出来的,比如要买 10 颗糖。
你可以用计算机测试一下,在这种包装情况下,最大不能买到的数量是17。大于17的任何数字都可以用4和7组合出来。
本题的要求就是在已知两个包装的数量时,求最大不能组合出的数字。
输入格式
两个正整数,表示每种包装中糖的颗数(都不多于1000)
输出格式
一个正整数,表示最大不能买到的糖数
样例输入1
4 7
样例输出1
17
样例输入2
3 5
样例输出2
7
分析:完全背包,且weight==value dp[i]为空间为i时能装的最大value, 从后往前找,如果dp[i]<i则找到该数字~
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
#include <iostream> #include <cmath> #include <vector> using namespace std; int main() { int t, n = 0, dp[100001] = {0}, maxn = 100000; vector<int> w(1), v(1); while (cin >> t) { w.push_back(t); v.push_back(t); n++; } for (int i = 1; i <= n; i++) { for (int j = w[i]; j <= maxn; j++) { dp[j] = max(dp[j], dp[j - w[i]] + v[i]); } } dp[0] = -1; for (int i = maxn; i >= 0; i--) { if (dp[i] < i) { cout << i; return 0; } } return 0; } |
❤ 点击这里 -> 订阅《PAT | 蓝桥 | LeetCode学习路径 & 刷题经验》by 柳婼