P1776 宝物筛选

bit manipulation,dp, https://www.luogu.com.cn/problem/P1776

【姚博骞 物院】思路：多重背包可以把物品总数拆成若干二进制个数的和，这样加和可以模拟所有可能的选择个数。

//将每个物品数量拆成二进制个数的01背包
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int max(int a,int b){
    return (a>b)?a:b;
}
int min(int a,int b){
    return (a<b)?a:b;
}
int main(){
    int n,wmax;
    cin>>n>>wmax;//n还未输入时不能用n初始化数组
    vector<int> v(n);
    vector<int> w(n);
    vector<int> m(n);
    vector<int>dp(wmax+1,0);
    for(int i=0;i<n;i++){
        cin>>v[i]>>w[i]>>m[i];   
    }
    for(int i=0;i<n;i++)//考虑要不要选这个物品
    {
        int num=min(wmax/w[i],m[i]);
        for(int k=1;num>0;k<<=1){
            int cnt=min(k,num);
            int value=cnt*v[i];
            int weight=cnt*w[i];
            for(int j=wmax;j>=weight;j--){
                dp[j]=max(dp[j-weight]+value,dp[j]);
            }
            num-=cnt;
        }
    }
    cout<<dp[wmax];
}