問(wèn)題描述：
現(xiàn)在給你一個(gè)容量為V的背包，有N個(gè)物品，其中第i件物品的重量為wi完全背包問(wèn)題算法，價(jià)值為vi，每件物品可以拿無(wú)數(shù)次，問(wèn)在有限的容量?jī)?nèi)，最多可以拿到多少價(jià)值的物品。
題目分析：
完全背包問(wèn)題和01背包好相似誒，不過(guò)貌似又不是那么一樣，對(duì)于完全背包問(wèn)題的每一個(gè)物品不是兩種狀態(tài)了，而是k+1種狀態(tài)：不拿或者拿1件或者拿2件或者....
剛開(kāi)始看到完全背包的問(wèn)題描述的時(shí)候，筆者腦海中還是蠻開(kāi)心的，這不就是貪心嗎？那我直接求性價(jià)比，用現(xiàn)在的包裹全部裝性價(jià)比最高的，然后用剩下的裝性價(jià)比第二高的...以此類推不就行了嘛。然而理想是美好的，但現(xiàn)實(shí)往往就是那么殘酷QAQ
稍微舉了個(gè)小案例，就發(fā)現(xiàn)貌似并不可以（當(dāng)然不可以，不然還要dp干啥...想想還是挺有道理的orz）就拿一個(gè)例子來(lái)說(shuō)：兩個(gè)物品分別是5 5和8 7（分別表示重量和價(jià)值），背包是10要是按照貪心策略，那肯定是7了完全背包問(wèn)題算法，但是答案卻是5+5=10。
好吧，貪心確實(shí)不好用。（蒟蒻的怒吼~）
還記得之前講過(guò)的01背包問(wèn)題嗎？當(dāng)時(shí)在用滾動(dòng)數(shù)組的思想去優(yōu)化的時(shí)候，是不是出現(xiàn)了正序和倒序的問(wèn)題？當(dāng)時(shí)模擬了一遍中間過(guò)程，發(fā)現(xiàn)不能正序，因?yàn)檎驎?huì)導(dǎo)致某一個(gè)物品被反復(fù)選擇...誒！這不正好是我們現(xiàn)在想要的嗎？（雀食蟀啊）
所以說(shuō)其實(shí)就只要吧01背包的倒序改為正序就變成了完全背包問(wèn)題了，至于原因，還是見(jiàn)01背包問(wèn)題關(guān)于倒序的手動(dòng)模擬部分
果然是車到山前必有路、世界是普遍聯(lián)系的、聯(lián)系具有客觀性、條件性、多樣性....（此人已瘋不用搭理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< 完全背包問(wèn)題，結(jié)束~