完全背包問題:

題目 有N種物品和一個容量為V的背包。第i種物品有若干件可用，每件費用是c[i]，價值是w[i]。求解將哪些物品裝入背包可使這些物品的費用總和不超過背包容量，且價值總和最大。

基本思路:

 這個問題和我們剛解決的01背包問題很像,不同的是該問題中的物品每一件有若干件,而01背包中的每一件物品只有一件.

動態規劃（DP）：

        1） 子問題定義：F[i][j]表示前i種物品中選取若干件物品放入剩余空間為j的背包中所能得到的最大價值。

        2） 根據第i種物品放多少件進行決策,我們可以將該問題轉化為01背包問題求解，對于特定的容量,每一件物品最多放V/C[i]件，然后按照01背包dp

dp[i][j]=max(dp[i][j],dp[i-1][j-k*need[i]]+k*value[i]);      (2-1)
        其中F[i-1][j-K*C[i]]+K*W[i]表示前i-1種物品中選取若干件物品放入剩余空間為j-K*C[i]的背包中所能得到的最大價值加上k件第i種物品；
       設物品種數為N，背包容量為V，第i種物品體積為C[i]，第i種物品價值為W[i]。
       與01背包相同，完全背包也需要求出NV個狀態F[i][j]。但是完全背包求F[i][j]時需要對k分別取0,…，j/C[i]求最大F[i][j]值,耗時為j/C[i]。那么總的時間復
雜度為O(NV∑(j/C[i]))
#include<bits/stdc++.h>using namespace std; const int maxn=555;int dp[maxn][111111];int need[maxn],value[maxn];int n,m;int main(){	int i,j,k;	while(~scanf("%d %d",&n,&m))	{		memset(dp,0,sizeof(dp));		for(i=1;i<=n;i++)			scanf("%d %d",&need[i],&value[i]); 		for(i=1;i<=n;i++)		{			for(j=0;j<=m;j++)			{				for(k=0;k*need[i]<=j;k++)						dp[i][j]=max(dp[i][j],dp[i-1][j-k*need[i]]+k*value[i]);			}		}		PRintf("%d/n",dp[n][m]);	}	return 0;}
	
  簡單優化：
        若兩件物品滿足C[i] ≤C[j]&&W[i] ≥W[j]時將第j種物品直接篩選掉。因為第i種物品比第j種物品物美價廉，用i替換j得到至少不會更差的方案。
       這個篩選過程如下：先找出體積大于背包的物品直接篩掉一部分（也可能一種都篩不掉）復雜度O(N)。利用計數排序思想對剩下的物品體積進行
排序，同時篩選出同體積且價值最大的物品留下，其余的都篩掉（這也可能一件都篩不掉）復雜度O(V)。整個過程時間復雜度為O(N+V)
 
       轉化為01背包：
       因為同種物品可以多次選取，那么第i種物品最多可以選取V/C[i]件價值不變的物品，然后就轉化為01背包問題。整個過程的時間復雜度并未減少。
如果把第i種物品拆成體積為C[i]×2k價值W[i]×2k的物品，其中滿足C[i]×2k≤V。那么在求狀態F[i][j]時復雜度就變為O(log2(V/C[i]))。整個時間復雜度就
變為O(NVlog2(V/C[i]))
時間復雜度優化為O(NV)
將原始算法的DP思想轉變一下。
設F[i][j]表示出在前i種物品中選取若干件物品放入容量為j的背包所得的最大價值。那么對于第i種物品的出現，我們對第i種物品放不放入背包
進行決策。如果不放那么F[i][j]=F[i-1][j]；如果確定放，背包中應該出現至少一件第i種物品，所以F[i][j]種至少應該出現一件第i種物品,
即F[i][j]=F[i][j-C[i]]+W[i]。為什么會是F[i][j-C[i]]+W[i]？因為我們前面已經最大限度的放了第i件物品,如果能放就放這最后的一件,
（或者理解為前面已經往背包中放入了第i件物品，我們每一次只增加一件的往背包里放,而且只能增加一件,多了放不下）
舉個例子:
比方有重量為2的物品, dp[i][2]的時候放了一件了,當dp[i][4]的時候,dp[i][4]=max(dp[i-1][4],dp[i][4-2]+w[i]) 最多一件了
狀態方程為：
                           (2-2)
#include<bits/stdc++.h>using namespace std; const int maxn=555;int dp[maxn][111111];int need[maxn],value[maxn];int n,m;int main(){	int i,j,k;	while(~scanf("%d %d",&n,&m))	{		memset(dp,0,sizeof(dp));		for(i=1;i<=n;i++)			scanf("%d %d",&need[i],&value[i]); 		for(i=1;i<=n;i++)		{			for(j=0;j<=m;j++)			{				if(j>=need[i])				dp[i][j]=max(dp[i-1][j],dp[i][j-need[i]]+value[i]);//注意和01背包的區別,這里是dp[i][j-need[i]]+value[i]				else				dp[i][j]=dp[i-1][j];			}		}		printf("%d/n",dp[n][m]);	}	return 0;}
優化空間復雜度為O（V）
        和01背包問題一樣，完全背包也可以用一維數組來保存數據。算法樣式和01背包的很相似，唯一不同的是對V遍歷時變為正序，而01背包為逆序
。01背包中逆序是因為F[i][]只和F[i-1][]有關，且第i件的物品加入不會對F[i-1][]狀態造成影響。而完全背包則考慮的是第i種物品的出現的問題，
第i種物品一旦出現它勢必應該對第i種物品還沒出現的各狀態造成影響。也就是說，原來沒有第i種物品的情況下可能有一個最優解，現在第i種物品
出現了，而它的加入有可能得到更優解，所以之前的狀態需要進行改變，故需要正序。
#include<bits/stdc++.h>using namespace std; const int maxn=555;int dp[111111];int need[maxn],value[maxn];int n,m;int main(){	int i,j,k;	while(~scanf("%d %d",&n,&m))	{		memset(dp,0,sizeof(dp));		for(i=1;i<=n;i++)			scanf("%d %d",&need[i],&value[i]); 		for(i=1;i<=n;i++)		{			for(j=need[i];j<=m;j++)			{				if(j>=need[i])				  dp[j]=max(dp[j],dp[j-need[i]]+value[i]);				}		}		printf("%d/n",dp[m]);	}	return 0;}
感謝！http://blog.csdn.net/wumuzi520/article/details/7014830