P1776 宝物筛选
___nyLittleT___
·
·
个人记录
题目传送门
题意
问容量为$W$的背包能装下最大多少价值的物品
### 上当受骗点
题面的习惯与我的习惯大相径庭，我常用$v$表示体积，$w$代表价值，因为数学的惯性思维
但是本题......
#### 恰恰相反
好吧我被骗了
大家一定要认真读题
## 解决方案
这里有好几种思路：
- 转化为$0/1$背包，每种物品看做独立的，共$\sum_{i=1}^{n}m_i$种物品，时间复杂度为$O(W\sum_{i=1}^{n}m_i)$，状态转移方程为：
$$dp[i][j]=max(dp[i-1][j],dp[i-1][j-k \times c[i]]+k \times w[i])$$
直接写三重循环，题中$1 \le n \le 100,n \le \sum m_i \le 10^5,0 \le W \le 4 \times 10^4 $，算出时间复杂度为$O(4 \times 10^4 \times 10^5)=O(4 \times 10^9)$，定要超时
- 二进制拆分优化
任意一个十进制整数$X$皆能由$2^k$相加得到，所以利用这个性质，总复杂度就能降到......
$$O(W \sum_{i=1}^{n}log_2(m_i))$$
算一下得到新时间复杂度为
$$O(4 \times 10^4 \times 17)=O(6.8 \times 10^5)$$
好了，上代码
```cpp
#include<bits/stdc++.h>
using namespace std;
int n,ww,ans,idx=1;
int w[1000005],v[1000005];
int dp[1000005]; //二进制拆分
int V,M,W;
int main() {
scanf("%d %d",&n,&ww);
for(int i=1; i<=n; i++) {
scanf("%d %d %d",&W,&V,&M);
for(int j=1; j<=M; j<<=1) {//二进制枚举：1,2,4,8,16,...
M-=j; //减去已拆分的
v[++idx]=j*V; //新物品
w[idx]=j*W;
}
if(M){
v[++idx]=V*M;
w[idx]=W*M;
}
}
//滚动数组
for(int i=1; i<=idx; i++) //枚举物品
for(int j=ww; j>=v[i]; j--) //背包容量
dp[j]=max(dp[j],dp[j-v[i]]+w[i]);
printf("%d",dp[ww]);
return 0;
}
```