- 1 秒
- 131,072 KB
- 40 分
- 4 级题
有N种物品，每种物品的数量为C1，C2......Cn。从中任选若干件放在容量为W的背包里，每种物品的体积为W1，W2......Wn（Wi为整数），与之相对应的价值为P1,P2......Pn（Pi为整数）。求背包能够容纳的最大价值。
收起
输入
第1行，2个整数，N和W中间用空格隔开。N为物品的种类，W为背包的容量。(1 <= N <= 100，1 <= W <= 50000)
第2 - N + 1行，每行3个整数，Wi，Pi和Ci分别是物品体积、价值和数量。(1 <= Wi, Pi <= 10000， 1 <= Ci <= 200)输出
输出可以容纳的最大价值。输入样例
3 6
2 2 5
3 3 8
1 4 1输出样例
9题意很简单，这是一个多重背包优化的模板题，我们来考虑这个个数c，显然任意一个整数，根据二进制可以由
1、2、4、8、16、32....这些数相加得到
那我们可以考虑把每份c分开，比如14个体积为v，价值为c的物品，我们可以分成
1 个 体积为v，价值为c的物品
1 个 体积为v * 2，价值为c * 2的物品
1 个 体积为v * 4，价值为c * 4的物品
1 个 体积为v * 7，价值为c * 7的物品
我们把所有的物品都分成这样，然后就可以看成一个01背包，直接跑一边就可以了
代码如下：
#include <bits/stdc++.h>
#include <time.h>
//#define first fi
//#define second seusing namespace std;typedef long long ll;
typedef double db;
int xx[4] = {1,-1,0,0};
int yy[4] = {0,0,1,-1};
const double eps = 1e-9;
typedef pair<int,int> P;
const int maxn = 2e6 + 5000;
const ll mod = 1e9 + 7;
inline int sign(db a) { return a < -eps ? -1 : a > eps;}
inline int cmp(db a,db b){ return sign(a - b);}
ll mul(ll a,ll b,ll c) { ll res = 1; while(b) { if(b & 1) res *= a,res %= c; a *= a,a %= c,b >>= 1; } return res;}
ll phi(ll x) { ll res = x; for(ll i = 2; i * i <= x; i++) { if(x % i == 0) res = x / i * (i - 1); while(x % i == 0) x /= i; } if(x > 1) res = res / x * (x - 1); return res;}
ll n,k;
int f[50050];
int c[50000];
int vv[50000];
int p[50000];
ll w;
vector<P>v;
int main() {ios::sync_with_stdio(false);while(cin >> n >> w){for(int i = 1;i <= n;i++) cin >> vv[i] >> p[i] >> c[i];memset(f,0,sizeof(f));v.push_back(P(0,0));for(int i = 1;i <= n;i++){for(int j = 1;j <= c[i]; c[i] -= j,j *= 2)v.push_back(P(vv[i] * j,p[i] *j));v.push_back(P(vv[i] * c[i],p[i] * c[i]));}
// for(auto d:v){cout << d.first << " " << d.second << endl;
// }for(int i = 1;i < v.size();i++){for(int j = w;j >= v[i].first;j--){f[j] = max(f[j],f[j - v[i].first] + v[i].second);}}cout << f[w] << endl;}//cout << "time: " << (long long)clock() * 1000 / CLOCKS_PER_SEC << " ms" << endl;return 0;
}