多重背包与二进制优化
<pre><code class="language-cpp">#include <iostream>
#include <cstring>
using namespace std;
typedef long long ll;
const int maxm = 100005;
ll v[maxm], w[maxm], cnt[maxm];
ll dp[maxm];
ll weight, value, cnt;
int main(){
cnts = m;
for(int i = 1; i <= m; i++){
scanf("%lld%lld%lld", &v[i], &w[i], &cnt[i]);
}
memset(dp, 0xc0, sizeof(dp)); //初始化
dp[0] = 0;
for(ll i = 1; i <= m; i++){
for(ll j = 1; cnt[i] >= j; j <<= 1){
++cnts;
v[cnts] = 1ll * v[i] * j;
w[cnts] = 1ll * w[i] * j;
cnt[i] -= j;
}
v[i] = 1ll * v[i] * cnt[i], w[i] = 1ll * w[i] * cnt[i];
}
for(ll i = 1; i <= cnts; i++){
for(ll j = weight; j >= w[i]; j--){
dp[j] = max(dp[j], dp[j-w[i]] + v[i]);
}
}
}</code></pre>