Description

清明君、五一君和六一君三個人是好朋友。

他們很喜歡去一家糖果店買糖果，糖果店有巧克力和草莓兩種口味的糖果出售。清明君喜歡吃巧克力味的糖果，六一君喜歡吃草莓味的糖果，五一君是個吃貨，兩種口味的糖果他都很喜歡吃。店老板把兩種口味的糖果混在一起裝在罐子里，于是每個罐子里每種糖果的數(shù)量都可能不相同。

這一天，清明君、五一君和六一君三個人去買糖果。他們的錢只能購買m罐糖果。清明君想要a顆巧克力味的糖果，六一君想要b顆草莓味的糖果，五一君則想要糖果的數(shù)量越多越好。五一君想知道在滿足清明君和六一君的要求下，自己最多能吃到多少顆糖果。

Input

輸入包含多組數(shù)據(jù)。

每組數(shù)據(jù)，第一行為兩個整數(shù)n,m(1<=m<=n<=100)，分別表示糖果店里糖果的總罐數(shù)和他們能夠買到糖果的罐數(shù)。

接下來有n行，每行兩個整數(shù)x,y(0<=x,y<=10)，表示第i罐糖果里有x顆巧克力味糖果和y顆草莓味糖果。

最后一行為兩個整數(shù)a,b。表示清明君想要a顆巧克力味的糖果，六一君想要b顆草莓味的糖果。

Output

每組測試數(shù)據(jù)輸出一個整數(shù)占一行，為五一君最多能吃到糖果的個數(shù)。如果沒有能滿足清明君和六一君要求的方案，則輸出-1。

Sample Input

3 2 1 10 3 2 3 4 5 3

Sample Output

4

思路：dp[i][j]代表的i罐糖果巧克力是j顆（j>=a或者<=suma)的情況下的最大草莓糖果

#include <stdio.h> #include <string.h> #include <algorithm> using namespace std; int dp[110][1100],a[110],b[110]; int n, m, x, y; int main() {while(~scanf("%d%d", &n, &m)){int ans=0;for(int i =0; i<n; i++){scanf("%d%d", &a[i], &b[i]);ans+=a[i];}scanf("%d%d",&x, &y);memset(dp, -1, sizeof(dp));dp[0][0]=0;for(int i = 0; i<n; i++){for(int j = m; j>=1; j--){for(int p=ans;p>=a[i]; p--){if(dp[j-1][p-a[i]]==-1)continue;dp[j][p]=max(dp[j-1][p-a[i]]+b[i],dp[j][p]); //當一開始的時候的dp[j][p]==-1.然后就會選中不符合條件的，因為dp[j-1][p-a[i]]+b[i]>0}}}int best=-1;for(int j=x;j<=ans;j++){if(dp[m][j]>=y&&(j+dp[m][j])>best){best=dp[m][j]+j;}}if(best==-1)puts("-1");elseprintf("%d\n",best-(x+y));}return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的二维费用 买糖果的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。