2018年網易實習生筆試題集合之牛牛的背包問題

問題描述，想必大家都知道01背包問題，現在的情況是問有多少種裝填背包的方式。

思考：昨晚想了一晚上沒能想明白用動态規劃這題該怎麼做，狀态轉移方程神馬的真不知道怎麼寫（希望評論大神給點助攻）

不用動态規劃這題怎麼思考呢？隻能暴力枚舉了，講道理枚舉都不是那麼好寫。

#include<bits/stdc++.h>
using namespace std;
int n,w;
vector<int> v;
int res = 0;
void dfs(int p,int q)
{
    if(p == n)
    {
        return;
    }
    dfs(p+1,q);//對第p件商品而言有放入何不放入兩種情況，這裡假定不放入
    if(q + v[p] <= w)
    {
        res++;
        dfs(p+1,q + v[p]);//
    }
}
int main()
{
    cin >> n >> w;
    for(int i = 0; i < n; ++i)
    {
        int vi;
        cin >> vi;
        v.push_back(vi);
    }
    dfs(0,0);
    cout << (res+1);
}
           

上面的代碼通過了60%的案例，意料之中，畢竟暴力枚舉怎麼可能直接過。

繼續思考：其實本質涉及背包問題的複雜度，動态規劃的複雜度是O（nV）n是商品的數量，V是背包的體積。我們注意到題目給的V實際上很大其實說白了這題能用動态規劃都不應該去用，因為複雜度可能也很大。窮舉的方式複雜度是2的n次方，題目中的n最大是30，是以其實也不行複雜度太大，那麼想辦法降低複雜度。但給出的錯誤在輸出上不是時間問題，很奇怪。

沒想明白回頭來填坑～～