[HOJ 176]小明買魚

HOJ生病惹QQ，因此我在這裡做了題目備份，請參考～

先備知識: 背包問題
這題看起來就是要叫我們用背包問題來解的樣子(?)
但是魚的總重量可以到一百多萬，魚又可以到幾十萬條，怎麼辦呢?
首先，對於重量都是w的魚，假設有N隻好了，那麼我們可以把這N條魚拆成1、2、4、8、...2^k、N-(2^(k+1)-1)條魚，這樣不管這種魚取多少條，一定可以從這些數字中找出一組符合的代表
為甚麼呢?
前面1、2、4、8、...2^k寫成二進位的話就變成一個1在不同的位數，任何<2 data-blogger-escaped-k="" data-blogger-escaped-n-="">N的情況也不會出現
這樣，我們魚的數量級就降為log(N)了
開始DP做背包問題，看看能湊出最接近重量一半的重量是多少

另外，問了別人0ms的做法，發現好像魚多到一種程度就不會再影響，可以把每種魚兩隻兩隻的拿掉直到剩下不太多又不少到WA，剩下的再來作背包
可是到底魚至少要留幾條才不至於WA呢?
我也不知道XD(我留了至少14條)
就等著大神來解惑吧~

code:

#include<cstdio>
#include<vector>
using namespace std;
int S[7],SUM,HALF;
vector<int>ITEM;
vector<bool>DP;
int main()
{
    SUM=0;
    for(int i=0;i<7;i++)scanf("%d",&S[i]),SUM+=(i+1)*S[i];
    HALF=SUM/2;
    ITEM.clear();
    for(int w=0;w<7;w++)
    {
        int remain=S[w];
        for(int i=0;(1<<i)<=remain;i++)
        {
            ITEM.push_back((w+1)*(1<<i));
            remain-=1<<i;
        }
        if(remain)ITEM.push_back((w+1)*remain);
    }
    DP.clear();DP.resize(HALF+1,false);
    DP[0]=true;
    for(const int v:ITEM)
    {
        for(int i=HALF;i-v>=0;i--)DP[i]=DP[i]|DP[i-v];
    }
    for(int i=HALF;i>=0;i--)if(DP[i])
    {
        printf("%d\n",(SUM-i)-i);
        break;
    }
    return 0;
}