本题是一道背包上限可以变化的多重部分和问题,此处给出了粗略题解
题目来源:(未知)
题面题目描述
llk经常和wy一起去yh小饭馆吃盖浇饭，一天他们吃完后llk把两个人的钱一起付了，但是wy不想欠llk的钱。
现在wy手中有一些散钱，llk手中也有一些散钱，wy想知道能不能刚好使得两不相欠，但是wy很笨，你能帮助wy吗？
输入
多组测试数据，每组第一行输入3个非负整数，C，n，m。C代表wy欠llk的钱，n代表wy手中钱面值的种类，m代表llk手中钱面值的种类。
接下来的n行，每行两个数v， c，分别代表wy手中面值为v的钱币有c个。再接下来的m行，每行两个数v，c，分别代表llk手中面值为v的钱币有c个。
（C <= 10000; 1<=n, m<50; 0<=v < =100; 0<=c<=10 ）
输出
每组数据输出一行，如果存在一种方案使得wy和llk两不相欠，输出YES，否则输出NO。
样例输入
7 1 1
10 1
1 10
样例输出
YES
提示
wy给了llk一张10元的，llk又给了wy三个1元的
参考代码
#include #include #include using namespace std;int main(){ ios::sync_with_stdio(false); int c, n, m; while (cin >> c >> n >> m) { pair *money = new pair[n + m]; // 存放输入的钱和数量 int limit = 0; // 背包容量可扩上限(因为llk会改变背包容量) // 输入钱的面值和数量 for (int i = 0; i > money[i].first >> money[i].second; if (i >= n) { limit += money[i].first * money[i].second; // 调整背包容量上限 } } // 初始状态 vector dp(c + limit + 1, -1); dp[0] = 0; // new一个数组是会re,所以此处用vector // 状态转移wy,状态定义为当前钱放满之后剩多少个,<0为放不了 for (int i = 0; i < n; i++) // 第i种钱 { for (int j = 0; j = 0) // 已经满了 { dp[j] = money[i].second; // 当前全部剩下 } else if (j < money[i].first || dp[j - money[i].first] <= 0) // 放不满 { dp[j] = -1; } else // 前面多出来的一个使之放满,所以剩下的少一个 { dp[j] = dp[j - money[i].first] - 1; } } } // 状态转移llk,状态定义为还能用第i种钱减小几次使得背包能放满,<0为减小了也放不了 for (int i = n; i = c; j--) // 用llk的钱来扩大背包总容量,需要当次后面的数据,所以要倒着 { if (dp[j] >= 0) // 已经满了 { dp[j] = money[i].second; // 当前全部剩下 } else if (j + money[i].first > c + limit || dp[j + money[i].first] <= 0) // 扩大不了 { dp[j] = -1; } else // 用前面多出来的一个扩大背包总容量,所以剩下的少一个 { dp[j] = dp[j + money[i].first] - 1; } } } cout <= 0 ? "YES" : "NO") << "\n"; // 检查下dp[c]的状态对不对即可 } return 0;}“正是我们每天反复做的事情，最终造就了我们，优秀不是一种行为，而是一种习惯” —亚里士多德
这里是浙江理工大学22届ACM集训队的成员一枚鸭!
本文首发于博客园，作者：星双子，除了我自己的转载请注明原文链接：https://www.cnblogs.com/geministar/p/repayment_of_debts.html