|
【算法分析】 多重背包问题通常可转化成01背包问题求解。但若将每种物品的数量拆分成多个1的话，时间复杂度会很高，从而导致TLE。所以，需要利用二进制优化思想。即： 一个正整数n，可以被分解成1,2,4,…,2^(k-1),n-2^k+1的形式。其中，k是满足n-2^k+1>0的最大整数。 例如，假设给定价值为2，数量为10的物品，依据二进制优化思想可将10分解为1+2+4+3，则原来价值为2，数量为10的物品可等效转化为价值分别为1*2，2*2，4*2，3*2，即价值分别为2，4，8，6，数量均为1的物品。【算法代码】
#include
using namespace std;
const int maxn=25000;
int N,V;
int w[maxn],v[maxn];
int dp[maxn];
int main() {
cin>>N>>V;
int cnt=0;
for(int i=1; i>wi>>vi>>s;
int k=1;
while(k0) {
cnt++;
w[cnt]=wi*s;
v[cnt]=vi*s;
}
}
N=cnt;
for(int i=1; i=w[i]; j--)
dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
}
cout |