题解
每次循环到第i
个物品,第j容量时
要比较 放1
个i
进去、放2
个i
进去…放c
个i进去这c个方案那种产生的价值最高
与其比较c
次 不如把c
分成 $log_2^{c}$ 组 比较分别放这 $log_2^{c}$ 组进去 那种最好
代码
#include<iostream>
using namespace std;
#include<algorithm>
const int N=2e4+10;//2048为2的20次方 意味着一种物品最多被分割为20种 那么物品种类极限为1000*20=2e4
int v[N],s[N],w[N],n,V,f[N],idx=1;
void init(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
}
//分割时要确保每一个数字都能被表示 比如当放1个时 放3个时 放7个时...
//只有从2^0=1,2^1=2,2^2=4...开始分割,最后剩下一个不满2^k的数字,这k+1组才能完整表示0~c所有的数量方案
//最后这个剩下的C可以故技重施地分割因此这种分割方法是可行的不会漏
void package(int a,int b,int c){
for(int i=0,inspect=1;inspect<=c;i++,inspect=inspect<<1){
v[idx]=inspect*a,w[idx++]=inspect*b,c-=inspect;
}
if(c){
v[idx]=c*a,w[idx++]=c*b;
}
}
int main(void){
init();
cin>>n>>V;
int a,b,c;
for(int i=1;i<=n;i++){
cin>>a>>b>>c;
package(a,b,c);
}
for(int i=1;i<idx;i++){
for(int j=V;j>=1;j--){
if(v[i]<=j) f[j]=max(f[j-v[i]]+w[i],f[j]);
}
}
cout<<f[V];
}