HDU 2159 FATE

系统管理员 2022-04-16 04:21 107阅读 0赞

## 原题目链接[HDU1505][] ##

--------------------

## 分类 ##

HDU 动态规划 背包 完全背包 二维背包

--------------------

## 题意 ##

（经典dp）完全背包 二维背包  
这题是完全背包，设f\[i\]\[j\]为杀第j只怪时耐久度为i的最大经验值，完全背包类型：有N种物品和一个容量为V 的背包，每种物品都有无限件可用。放入第i种物品的耗费的空间是Ci，得到的价值是Wi。求解：将哪些物品装入背包，可使这些物品的耗费的空间总和不超过背包容量，且价值总和最大。

Sample Input

10 10 1 10
    1 1
    10 10 1 9
    1 1
    9 10 2 10
    1 1
    2 2

Sample Output

0
    -1
    1

--------------------

## 想法 ##

于dp题目，需要找出限制条件，比如这道题目的限制条件是 1.拥有的耐久度 2.最多打怪数目  
就需要两层循环来循环这两个条件，另一层循环来循环物品种类 3层循环  
一般的01背包，只有两层循环，是一维背包， 这道题是二维背包

\*\*多想 0 - 1 背包怎么做的， 多维背包其实是相通的！！！ \*\*

--------------------

## 代码 ##

31ms

#include <bits/stdc++.h>
    using namespace std;
    const int maxn  = 111;
    int n , m, k, s;
    int a[maxn],b[maxn],dp[maxn][maxn];//dp[i][j] : 打怪数目为i，耐久度消耗为j时的最大经验值 
    /** 对于dp题目，需要找出限制条件，比如这道题目的限制条件是 拥有的耐久度 最多打怪数目 就需要两层循环来循环这两个条件，另一层循环来循环物品种类 3层循环 一般的01背包，只有两层循环，是一维背包， 这道题是二维背包 */ 
    
    
    /** * 多想 0 - 1 背包怎么做的， 多维背包其实是相通的！！！ */
    
    int main() { 
    	while(cin >> n >> m >> k >> s)//需要的经验值 拥有的耐久度 怪物种类 最多打怪数目 
    	{ 
    		for(int i =0;i < k;i++)
    		{ 
    			cin >> a[i] >> b[i];//经验 需要的耐久度 
    		}
    		memset(dp,0,sizeof(dp));
    		for(int p = 0;p < k;p++)//循环怪物种类 
    		{ 
    			for(int i =1;i <= s;i++)//循环打怪数量 
    			{ 
    				for(int j =b[p];j <= m;j++)//循环耐久度 
    				{ 	
    					dp[i][j] = max(dp[i][j],dp[i-1][j - b[p]] + a[p]);
    				}
    			}
    		}
    		
    		int flag = 0;
    		for(int i =1;i <= m;i++)
    		{ 
    			//for(int j =1;j <= s;j++)
    			//{ 
    				if(dp[s][i] >= n)
    				{ 
    					flag = 1;
    					printf("%d\n",m - i);
    					goto loop;
    				}
    			//}
    		}
    		loop:
    			if(!flag)
    			{ 
    				printf("-1\n");
    			}
    	}
    	return 0;
    }

[HDU1505]: http://acm.hdu.edu.cn/showproblem.php?pid=2159