众所周知, 背包非常简单,所以可以把这道题转换为 背包解决。
具体的:
对于 的,视为最多能取 个
对于 的,视为最多能取 个
将有限个物品拆分,例如 ,存到数组里,然后就可以跑 背包啦
#include<bits/stdc++.h>
using namespace std;
int dp[50005],w[50005],v[50005];
int cnt=0;
void add(int ww,int vv,int c){
while(c--){
w[++cnt]=ww;
v[cnt]=vv;
}
}
int main(){
int V,n;
cin>>V>>n;
for(int i=1;i<=n;i++){
int ww,vv,c;
cin>>ww>>vv>>c;
if(c==0||c>V/ww){
c=V/ww;
}
add(ww,vv,c);
}
for(int i=1;i<=cnt;i++){
for(int j=V;j>=w[i];j--){
dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
}
}
cout<<dp[V]<<endl;
return 0;
}
题外话:为什么其他题解都只有代码(