欧美vvv,亚洲第一成人在线,亚洲成人欧美日韩在线观看,日本猛少妇猛色XXXXX猛叫

問題描述：

現在給你一個容量為V的背包，有N個物品，其中第i件物品的重量為wi完全背包問題算法，價值為vi，每件物品可以拿無數次，問在有限的容量內，最多可以拿到多少價值的物品。

題目分析：

完全背包問題和01背包好相似誒，不過貌似又不是那么一樣，對于完全背包問題的每一個物品不是兩種狀態了，而是k+1種狀態：不拿或者拿1件或者拿2件或者....

剛開始看到完全背包的問題描述的時候，筆者腦海中還是蠻開心的，這不就是貪心嗎？那我直接求性價比，用現在的包裹全部裝性價比最高的，然后用剩下的裝性價比第二高的...以此類推不就行了嘛。然而理想是美好的，但現實往往就是那么殘酷QAQ

稍微舉了個小案例，就發現貌似并不可以（當然不可以，不然還要dp干啥...想想還是挺有道理的orz）就拿一個例子來說：兩個物品分別是5 5和8 7（分別表示重量和價值），背包是10要是按照貪心策略，那肯定是7了完全背包問題算法，但是答案卻是5+5=10。

好吧，貪心確實不好用。（蒟蒻的怒吼~）

還記得之前講過的01背包問題嗎？當時在用滾動數組的思想去優化的時候，是不是出現了正序和倒序的問題？當時模擬了一遍中間過程，發現不能正序，因為正序會導致某一個物品被反復選擇...誒！這不正好是我們現在想要的嗎？（雀食蟀啊）

所以說其實就只要吧01背包的倒序改為正序就變成了完全背包問題了，至于原因，還是見01背包問題關于倒序的手動模擬部分

果然是車到山前必有路、世界是普遍聯系的、聯系具有客觀性、條件性、多樣性....（此人已瘋不用搭理qwq）

所以我們只需要把倒序改為正序，就可以咯，代碼如下...

#include
#include

#include
using namespace std;
const int MAXN=1e3+7;
int w[MAXN],N,V,v[MAXN],dp[100001];
int main()
{

    memset(dp,0,sizeof(dp));
    cin>>V>>N;
    for(int i=1;i<=N;i++)
    {
        cin>>w[i]>>v[i];
    }

    for(int i=1;i<=N;i++)
    {
        for(int j=0;j<=V;j++)
        {
            if(j>=w[i])
                dp[j]=max(dp[j],dp[j-w[i]]+v[i]);	

        }
    }
    cout<