2017-12-21

題目描述

給一個nums[]數組,如[1, 2, 4] 將這些數組合使得： 這些數的和是給出的一個target，如使這些數的和等于4，求這樣的組合有多少個？

樣例

樣例 [1, 1, 1, 1] [1, 1, 2] [1, 2, 1] [2, 1, 1] [2, 2] [4]這些組合都可以，他們的和都是4 所以答案是6

解題思路

我們根據給的樣例來看，我們是考慮順序的，因此我們的[1，1，2]與[1,2,1]與[2,1,1]是三種不同的情況... 首先很容易想到的是深搜 #include<iostream> using namespace std;const int N = 100; int x[N+1]; int sum,res,n;void dfs(int s){if (s>sum) return ;if (s==sum) {res++;return ;}for (int i=0;i<n;i++){dfs(s+x[i]);} }int main(){cin>>n;for (int i=0;i<n;i++){cin>>x[i];}while (cin>>sum){res=0;int s=0;dfs(s);cout<<res<<endl;}return 0; } 因為每一個數可以用多次，所以我們在dfs里面的循環每次都是從1開始的... 嗯，我們應該也可以想到，如果我們能夠先對我們輸入的數組進行排序的話，那么我們應該就可以提前跳出循環了吧 #include<iostream> using namespace std;const int N = 100; int x[N+1]; int sum,res,n;void dfs(int s){if (s>sum) return ;if (s==sum) {res++;return ;}for (int i=0;i<n;i++){if (s+x[i]>sum) return ;dfs(s+x[i]);} }int main(){cin>>n;for (int i=0;i<n;i++){cin>>x[i];}while (cin>>sum){res=0;int s=0;dfs(s);cout<<res<<endl;}return 0; } 嗯，最后就是用動態規劃了！首先我們應該可以假設dp[n]為和為n時所有的情況，對于我們所給的例子而言，dp[4]=dp[3]+dp[2]+dp[0]，其實就是等同于我們第一個數可以為1,2,4，如果第一個數為1的話，又等同于dp[3]=dp[2]+dp[1]，如果第一個數為2的話，又等同于dp[2]=dp[1]+dp[0]，如果第一個數為4的話，就等同于dp[0]，那么我們我們可以給出方程dp[i]+=dp[i-x[j]]... #include<iostream> #include<cstring> using namespace std;const int N = 100; int x[N+1],dp[N+1]; int sum,n;void cal(){dp[0]=1;for (int i=1;i<=sum;i++){for (int j=0;j<n;j++){if (i-x[j]>=0){dp[i]+=dp[i-x[j]];}}} }int main(){cin>>n;for (int i=0;i<n;i++){cin>>x[i];}while (cin>>sum){memset(dp,0,sizeof(dp));cal();cout<<dp[sum]<<endl;}return 0; }

總結

以上是生活随笔為你收集整理的九章算法 | Facebook 面试题 : Backpack VI 背包算法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。