# 多重背包问题 II

###### tags: `競程題解`,`競程`

題敘：

如果硬幹的話 把每一個物件切分成1個一個下去丟背包
那複雜度會是 $O(N*2000*V)$ 大約在 $O(4e9)$ 左右 非常危險 但我丟上去 甚至沒加 IO 還是 AC 了 XD

那要怎麼想呢

很簡單 把每個物件拆成 2^n 個就好了
例如 a 物件有 11 個
那麼我們就把他拆成 1+2+4+4 個 然後下去丟背包
可以稍微嘗試一下 1,2,4,4 是可以組出 1~11中的任意數的

更深入的解釋：

拿剛剛的例子 11
為什麼不能拆成 1 2 4 8 呢 很簡單 因為假設選 4,8 好了
那就會超過題目給的11 那就不行了

那要怎麼做呢

int n=1;
while(k-n>=0){
    k-=n;
    pb.push_back(n);
    n*=2;
}
if(k)pb.push_back(k);

這樣的話 11 就會被拆成 1,2,4,4

可以看到 1,2,4 可以組合成 1~7中"任意"一個數
加上四後 如果想組出 10
那麼 就先從剛剛的 1,2,4 中 組出 6 然後直接加最後的4即可
其他大於7的數也是同理。

如果上面的還是不太懂的話，可以看一下另一個解釋方法

拆成 1,2,4,4 後 只要是想要組出 >7的數 那就直接把最後弄出來的4減掉 剩下的數一定小於等於7
1,2,4就可以隨便把7組合出來了!

#include "iostream"
#include "vector"
using namespace std;
int main(){
    int dp[10010]={};
    int n,v,val,w;
    cin>>n>>v;
    int ans=0;
    for(int j=0;j<n;j++){
        int k;
        cin>>w>>val>>k;
        vector<int> pb;
        int n=1;
        while(k-n>=0){
            k-=n;
            pb.push_back(n);
            n*=2;
        }
        if(k)pb.push_back(k);
        
        for(int j:pb){
            for(int i=v;i>=w*j;i--){
                if(dp[i]<dp[i-w*j]+val*j){
                    dp[i]=max(dp[i],dp[i-w*j]+j*val);
                }
                ans=max(ans,dp[i]);
            }
        }
        
    }
    cout<<ans;
}

後來晚上剛好翻到資芽的講義