本文主要是介绍HDU 2191 珍惜现在，感恩生活，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
多重背包。
超过总价钱的是完全背包。 少于总价钱的 用 二进制优化然后按照0 1背包做。
用 d【i】 = j 表示 当价钱为 i 时 做多有多重的米。
具体实现代码。
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <string>
#include <map>
#include <vector>
#include <set>
#include <queue>
#include <stack>
#include <cctype>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
#define MAXN 100+10
#define INF (1<<30)
#define mod 123456789
struct now{int p; // 每袋价格int h; // 每袋的重量int c; // 袋数
};
int main (){int t;scanf("%d",&t);while(t--){int n,m;scanf("%d%d",&n,&m);now s[MAXN];for(int i = 1; i <= m; i++)scanf("%d%d%d",&s[i].p,&s[i].h,&s[i].c);LL d[4000] = {0};d[0] = 0;for(int i = 1; i <= m; i++){if(s[i].c*s[i].p >= n){for(int k = s[i].p; k <= n; k++)if(d[k-s[i].p] || k-s[i].p == 0)d[k] = max(d[k],d[k-s[i].p]+s[i].h);}else{int j;for(j = 1; j <= s[i].c/2; j = (j<<1)){for(int k = n; k >= s[i].p*j; k--){if(d[k-s[i].p*j] || k-s[i].p*j == 0)d[k] = max(d[k-s[i].p*j]+s[i].h*j,d[k]);}}int x = s[i].c+1-j;for(int k = n; k >= s[i].p*x; k--){if(d[k-s[i].p*x] || k-s[i].p*x == 0)d[k] = max(d[k-s[i].p*x]+s[i].h*x,d[k]);}}}LL ma = 0;for(int i = n; i >= 0; i--)ma = max(ma,d[i]);printf("%I64d\n",ma);}return 0;
}
这篇关于HDU 2191 珍惜现在，感恩生活的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
