0-1部分和
- 問題描述：有n個大小不同的數字a，判斷是否能從中取出若干個數，使得這些數的和為k。
- 解決思路：利用DFS(深度優先搜索)來解決，用dfs(i,j)表示前i個數字能否得到部分和j,則根據前i+1個數的能否得到部分和j或j+a[i+1]來判斷dfs(i,j)的狀態，算法如下：
1 bool dfs(int i,int sum) 2 { 3 if(i==n) return sum==k; 4 if(dfs(i+1,sum)) return true; 5 if(dfs(i+1,sum+a[i+1])) return true; 6 return false; 7 }
或者也可以將此問題轉化為0-1背包問題求解，第i件物品的重量和價值均為a[i]，判斷能否恰好將某些物品放入容量為k的背包中。
多重部分和
- 問題描述：有n個大小不同的數字a，每個數有m個，判斷能否從中取出若干個數，使得這些數的和為k。
- 方法1：利用動態規劃求解，dp[i][j]表示前i個數能否構成部分和j，時間復雜度為O(nkm)算法如下：
1 dp[n+1][k+1]; 2 dp[0][0]=1; 3 4 for(int i=0; i<n; i++) 5 for(int j=0; j<=k; j++) 6 for(int s=0; s<=m[i]&&s*a[i]<=j; s++) 7 dp[i+1][j] |= dp[i][j-s*a[i]];
- 方法2：利用動態規劃求解，dp[i][j]表示用前i個數得到部分和時，第i個數最多能剩余多少個，dp[i][j]被初始化為-1，dp[i][j]>-1表示前i個數能得到部分和j,算法的偽代碼如下：
if dp[i-1][j]>=0 dp[i][j]=m[i]; else if(a[i]>j || dp[i][j-a[i]])<=0) dp[i][j]=-1; else dp[i][j]=dp[i][j-a[i]]-1;
對以上算法可以優化空間復雜度，用cn[j]表示狀態dp[i][j]，則算法如下：
1 memset(cn,-1,sizeof(cn)); 2 dp[0]=0; 3 4 for(int i=0; i<n; i++) 5 for(int j=0; j<=k; j++) 6 if(dp[j]>=0) dp[j]=m[i]; 7 else if(j<a[i] || dp[j-a[i]]<=0) dp[j]=-1; 8 else dp[j]=dp[j-a[i]]-1;
?
)
