本題是一道背包上限可以變化的多重部分和問題,此處給出了粗略題解
題目來源:(未知)
題面
題目描述
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 <iostream>
#include <cstring>
#include <vector>
using namespace std;
int main()
{
ios::sync_with_stdio(false);
int c, n, m;
while (cin >> c >> n >> m)
{
pair<int, int> *money = new pair<int, int>[n + m]; // 存放輸入的錢和數量
int limit = 0; // 背包容量可擴上限(因為llk會改變背包容量)
// 輸入錢的面值和數量
for (int i = 0; i < n + m; i++)
{
cin >> money[i].first >> money[i].second;
if (i >= n)
{
limit += money[i].first * money[i].second; // 調整背包容量上限
}
}
// 初始狀態
vector<int> 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 <= c + limit; j++) // 背包上限為j
{
if (dp[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 < m + n; i++) // 第i種錢
{
for (int j = c + limit; j >= 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 << (dp[c] >= 0 ? "YES" : "NO") << "\n"; // 檢查下dp[c]的狀態對不對即可
}
return 0;
}
"正是我們每天反復做的事情，最終造就了我們，優秀不是一種行為，而是一種習慣" ---亞里士多德
這里是浙江理工大學22屆ACM集訓隊的成員一枚鴨!
本文首發于博客園，作者：星雙子，除了我自己的轉載請注明原文鏈接：https://www.cnblogs.com/geministar/p/repayment_of_debts.html
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/536235.html
標籤：其他
上一篇：深度學習之卷積模型應用