HDU 2844 Coins (多重背包->類01背包優化)

(TEST<31> 11.20)

解題思路

看着就是 多重背包問題 在這裡 進行了

0/1背包的優化

用dp【價值】=所能達到的最大價值

來判定是否能夠達到 這個 值

關于0/1背包優化 解析

（出自ACwing 基礎算法視訊第五章 第一節動态規劃 ）

看 1023 數字之和能夠組成 1023？ 0-1023 枚舉每一個

顯然 是暴力

如果将其分成幾組的話

1，2，4，8…512 一共 10組 每組

這樣 看錯 0/1背包在每一組 dp【】更新的時候就會

周遊所有0-1023的多有值

組号	周遊範圍	組内數字	組内周遊值
第一組	0~1	1	0，1
第二組	0~3	2	2，3
第三組	0~7	4	4，5，6，7
…	…	…	…
第十組	0~1023	512	512~1023

或許有人會問 會不會出現 dp[i]>i的情況

這種情況不會出現 ，dp[i]更新依賴于

dp[i]=max(dp[i],dp[i-value]+value);

這樣每次更新 都依靠前面的值

最前的初始值 dp[0]=0；

又因為你值的更新程度就等于

你坐标變化的量是以不會超過。

AC 代碼如下

#include<iostream>
#include <cstring>
#include<cstdio>
#include<cmath>
using namespace std;
int v,w;
int val[105],num[105];
int  dp[100000+5];
void pack(int value, int number){
     //完全背包模型
        if(value*number>=w){
        for(int i=value; i<=w;i++){
            dp[i]=max(dp[i],dp[i-value]+value);
        }
    }else{
    //0/1背包模型
        //優化 0/1背包
        int k=1; 
        int nc=number;
        while(k<nc){
            for(int i=w;i>=k*value;i--)
            dp[i]=max(dp[i],dp[i-k*value]+k*value);
            nc-=k;
            k*=2;
            }
            //優化0/1背包 ->周遊 優化2^k餘下的硬币個數
        for(int i=w;i>=nc*value;i--){
            dp[i]=max(dp[i],dp[i-nc*value]+nc*value);
        }
    }  
}
int main(){
    while(~scanf("%d%d%",&v,&w)&&v&&w){
        memset(dp,0,sizeof(dp));
        for(int i=0;i<v;i++){
            scanf("%d",&val[i]);
        }
        for(int i=0;i<v;i++){
            scanf("%d",&num[i]);
        }
        for(int i=0;i<v;i++){
            pack(val[i],num[i]);
        }
    int ans=0; 
    for(int i=1;i<=w;i++){
        if(dp[i]==i)
        ans++;
        }
    printf("%d\n",ans);
    }
    return 0;
}