HDU 2191 悼念512汶川大地震遇难同胞——珍惜现在，感恩生活

秒速五厘米 2022-04-16 07:10 138阅读 0赞

## 原题目链接：[HDU2191][] ##

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

## 分类 ##

HDU 动态规划 背包 0-1背包 完全背包

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

## 题意 ##

看题就可以理解了，不难

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

## 想法 ##

1.  0-1背包
2.  多重背包

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

## 代码 ##

15ms  
0-1背包

/** * Author: GatesMa * Email: gatesma@foxmail.com * Todo: ACM Training * Date:2018/11/18 */
    #include <bits/stdc++.h>
    using namespace std;
    const int INF=0x3f3f3f3f;
    const int maxn = 111; 
    
    int dp[maxn];
    int n, m, t;
    int weight[maxn];
    int cost[maxn];
    int num[maxn];
    /** 这个做法是0-1背包做的 反正不管怎么样，最外面一层一定是种类 最里面一层一点是money */
    int main()
    { 
    	cin >> t;
    	while( t-- )
    	{ 
    		memset(dp, 0, sizeof(dp));
    		cin >> n >> m;
    		for(int i=1; i <=m; i++)
    		{ 
    			cin >> cost[i] >> weight[i] >> num[i];
    		}
    		for(int i =1;i<=m ;i++)//循环种类 
    		{ 
    			for(int j=1;j <= num[i]; j++)//循环选择个数 
    			{ 
    				for(int k =n;k>=cost[i]; k--)//循环钱 
    				{ 
    					dp[k] = max(dp[k], dp[k-cost[i]]+weight[i]);
    				}
    			}
    		}
    		cout << dp[n] << endl;
    	}
        return 0;
    }

另一种做法

/** * Author: GatesMa * Email: gatesma@foxmail.com * Todo: ACM Training * Date:2018/11/18 */
    #include <bits/stdc++.h>
    using namespace std;
    const int INF=0x3f3f3f3f;
    const int maxn = 111; 
    
    int dp[maxn];
    int n, m, t;
    int weight[maxn];
    int cost[maxn];
    int num[maxn];
    /** 这个做法是0-1背包做的 反正不管怎么样，最外面一层一定是种类 最里面一层一点是money */
    int main()
    { 
    	cin >> t;
    	while( t-- )
    	{ 
    		memset(dp, 0, sizeof(dp));
    		cin >> n >> m;
    		for(int i=1; i <=m; i++)
    		{ 
    			cin >> cost[i] >> weight[i] >> num[i];
    			for(int j=1;j <= num[i]; j++)//循环选择个数 
    			{ 
    				for(int k =n;k>=cost[i]; k--)//循环钱 
    				{ 
    					dp[k] = max(dp[k], dp[k-cost[i]]+weight[i]);
    				}
    			}
    		}
    		cout << dp[n] << endl;
    	}
        return 0;
    }

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

[HDU2191]: http://acm.hdu.edu.cn/showproblem.php?pid=2191