2016年1月9日 星期六

[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;
}

沒有留言:

張貼留言

歡迎留言或問問題~
若您的留言中包含程式碼,請參考這篇
如果留言不見了請別慌,那是因為被google誤判成垃圾留言,小莫會盡快將其手動還原