01背包是指每件物品有且只有一件偶垮，而完全背包則是每件物品件數(shù)無限导饲，求裝入背包所對(duì)應(yīng)的最值。
完全背包也有公式程剥，在01背包公式的基礎(chǔ)上加以改動(dòng)迫摔。
完全背包公式：dp [ j ] =min/max( dp[ j ] ,dp [ j - w [ i ] ] + v [ i ] ) 沐扳。
從公式看出，完全背包相較于01背包句占，dp數(shù)組由二維變成一維沪摄，但整個(gè)過程和01背包大同小異。第一步仍然是對(duì)數(shù)組進(jìn)行初始化操作纱烘，題目不同初始化操作不同杨拐，求最大值需要將dp[ ]全設(shè)為無窮小，求最小值則初始化為無窮大擂啥。公式本身不難理解哄陶，j還是代表重量為j，i是外層循環(huán)哺壶，表示目前裝到第i種物品屋吨。dp[ j - w[ i ] ]就是當(dāng)重量為j時(shí)少裝一件物品i時(shí)的最高價(jià)值，那么裝了物品i后山宾，價(jià)值自然變?yōu)閐p[ j - w[ i ] ] + v[ i ]至扰，與當(dāng)前dp[ j ]比較取符合題意的結(jié)果即可。
給出一道例題加以分析塌碌。
典例：http://acm.hdu.edu.cn/showproblem.php?pid=1114
題意：給出存錢罐空時(shí)的重量和裝滿時(shí)的重量渊胸，給出n種錢幣的價(jià)值和重量，求存錢罐裝滿時(shí)所能達(dá)到的最小價(jià)值
分析：從第一個(gè)開始遍歷台妆，從重量 j >=w[ i ] 開始計(jì)算翎猛，比較裝下物品 i 后的價(jià)值和沒裝 i 時(shí)的價(jià)值選最優(yōu)解。因?yàn)楸嘲仨氀b滿接剩，故最終輸出dp[ full - Empty ]的價(jià)值切厘。
#include <iostream>
#include <string.h>
#include <stdio.h>
#include <algorithm>
#include <math.h>
#define INF 1000000001
using namespace std;
int w[505],v[505],dp[10005];
int main()
{
int T,n,m,Empty,full;
cin>>T;
while(T--)
{
cin>>Empty>>full;
m=full-Empty; //m表示存錢罐能裝錢幣的重量
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>v[i]>>w[i];
}
dp[0]=0;
for(int i=1;i<=m;i++)//dp數(shù)組初始化
dp[i]=INF;
for(int i=1;i<=n;i++) //i從1到n表示n種錢幣
for(int j=w[i];j<=m;j++) //注意j從w[ i ]開始，不然會(huì)
dp[j]=min(dp[j],dp[j-w[i]]+v[i]);
if(dp[m]<INF) cout<<"The minimum amount of money in the piggy-bank is "<<dp[m]<<"."<<endl;
else cout<<"This is impossible."<<endl;
}
return 0;
}
