石を分ける
質問c:【再帰入門】石を分ける
時間制限:1 Secメモリ制限:128 MBコミット:27解決:20[コミット][ステータス][ディスカッション版][命題者:外部インポート]
タイトルの説明
n個の石があり、それらの重量はそれぞれW 1,...,Wn.
2つの石の重さの差が最小になるように、プログラムを書いて、それらを2つの山に分けます.
入力
n(1≦n≦20)を入力して石の個数を表す.
2行目n個の石の重量W 1,...,Wn(1≦Wi≦100000)
しゅつりょく
最小の差を入力(絶対値)
サンプル入力
サンプル出力
時間制限:1 Secメモリ制限:128 MBコミット:27解決:20[コミット][ステータス][ディスカッション版][命題者:外部インポート]
タイトルの説明
n個の石があり、それらの重量はそれぞれW 1,...,Wn.
2つの石の重さの差が最小になるように、プログラムを書いて、それらを2つの山に分けます.
入力
n(1≦n≦20)を入力して石の個数を表す.
2行目n個の石の重量W 1,...,Wn(1≦Wi≦100000)
しゅつりょく
最小の差を入力(絶対値)
サンプル入力
5
5
8
13
27
14
サンプル出力
3
#include
#include
#include
#include
#include
#define inf 0x3f3f3f3f
using namespace std;
int n,ans=inf,w[20],sum=0;//ans
void dfs(int xb,int sum1)//xb ,sum1
{int sum2=sum-sum1;//sum2
if(xb==n-1)
{
ans=min(ans,abs(sum1-sum2));// ,
return;
}
dfs(xb+1,sum1+w[xb]);// a[xb]
dfs(xb+1,sum1);// a[xb]
}
int main()
{
cin>>n;
for(int i=0;i>w[i];
sum+=w[i];
}
dfs(0,0);
cout<