Food Problem

Time Limit: 3000/2000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others)

Total Submission(s): 1243 Accepted Submission(s): 368

Problem Description

Few days before a game of orienteering, Bell came to a mathematician to solve a big problem. Bell is preparing the dessert for the game. There are several different types of desserts such as small cookies, little grasshoppers and tiny mantises. Every type of dessert may provide different amounts of energy, and they all take up different size of space.

Other than obtaining the desserts, Bell also needs to consider moving them to the game arena. Different trucks may carry different amounts of desserts in size and of course they have different costs. However, you may split a single dessert into several parts and put them on different trucks, then assemble the parts at the game arena. Note that a dessert does not provide any energy if some part of it is missing.

Bell wants to know how much would it cost at least to provide desserts of a total energy of

Input

The first line of input contains a integer

Output

For every test case output the minimum cost to provide the dessert of enough energy in the game arena if it is possible and its cost is no more than

Sample Input

4 1 1 7 14 2 1 1 2 2 1 1 10 10 10 1 5 7 2 5 3 34 1 4 1 9 4 2 5 3 3 1 3 3 5 3 2 3 4 5 6 7 5 5 3 8 1 1 1 1 2 1 1 1 1

Sample Output

4 14 12 TAT

/*hdu 5445 多重背包problem:给一场运动会提供食物，每种食物提供ti能量，占用vi空间，最多可提供ui个，把食物运到指定地点，每种车可以运送ai体积的食物，消耗bi的金钱，总共有ci个这种车，问给运动会提供至少p的能量，最少需要花多少运费(每个食物可以拆开来运)solve:可以将其分成两个多重背包计算,先计算出运送指定能量的食物最少需要多少的空间,然后在这个空间的基础上计算最少需要的花费.结果RE,后来发现这个空间可能很大.而题目中说了50000这个界限,所以直接计算出50000的花费能够达到的最大空间hhh-2016-08-17 15:13:15*/#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           #define lson i<<1#define rson i<<1|1#define ll long long#define key_val ch[ch[root][1]][0]using namespace std;const int maxn = 1010;const int inf = 0x3f3f3f3f;int dp[51000];int ta,a,c;void cal_min(int cost,int val,int num,int m){ if(cost * num >= m) { for(int i = cost; i <= m; i++) { dp[i] = min(dp[i],dp[i-cost] + val); } } else { int k = 1; while(k < num) { for(int i = m; i >= cost*k; i--) dp[i] = min(dp[i],dp[i-cost*k]+val*k); num -= k; k *= 2; } for(int i = m; i >= cost*num; i--) dp[i] = min(dp[i],dp[i-cost*num]+val*num); }}void cal_max(int cost,int val,int num,int m){ if(cost * num >= m) { for(int i = cost; i <= m; i++) { dp[i] = max(dp[i],dp[i-cost] + val); } } else { int k = 1; while(k < num) { for(int i = m; i >= cost*k; i--) dp[i] = max(dp[i],dp[i-cost*k]+val*k); num -= k; k *= 2; } for(int i = m; i >= cost*num; i--) dp[i] = max(dp[i],dp[i-cost*num]+val*num); }}int main(){// freopen("in.txt","r",stdin); int n,m,cnt; int T; cin >> T; while(T--) { memset(dp,inf,sizeof(dp)); dp[0] = 0; scanf("%d%d%d",&n,&cnt,&m); for(int i = 1; i <= n; i++) { scanf("%d%d%d",&a,&c,&ta); cal_min(a,c,ta,m + 100); //因为每个能量最多100,所以最大界限为m+100 } int minpart = inf; for(int i = m; i <= m+100; i++) { minpart = min(minpart,dp[i]); }// cout <<"m:" <
            
             <<" min:"<
             
              <
              
               <= 50000;i++){ if(dp[i] >= minpart) { ans = i; break; } } if(ans == inf) printf("TAT\n"); else printf("%d\n",ans); } return 0;}

转载于:https://www.cnblogs.com/Przz/p/5792161.html

你可能感兴趣的文章