pascal 石子合并:有n堆石头质量分别为W1,W2,……,Wn(W≤100 000).现在需要你将石头合并为两部分,使
问题描述:
pascal 石子合并:有n堆石头质量分别为W1,W2,……,Wn(W≤100 000).现在需要你将石头合并为两部分,使
有n堆石头质量分别为W1,W2,……,Wn(W≤100 000).现在需要你将石头合并为两部分,使两部分的质量之和最接近.
代码如下:
var ans,sum,i,k,n:longint;
w:array[0..20]of longint;
function min(a,b:longint):longint;
begin
if a>b then exit(b) else exit(a);
end;
procedure dfs(k,tot:longint);
begin
if (tot*2>=sum)or(k>n)then
begin
ans:=min(ans,abs(sum-tot-tot));
exit;
end;
dfs(k+1,tot+w[k]);
dfs(k+1,tot);
end;
begin
ans:maxlongint;
sun:=0;
read(n);
for i:=1 to n do
begin
read(w[i]);
inc(sum,w[i]);
end;
dfs(1,0);
writeln(ans);
end.
dfs(1,0)
为什么初始化是1和0?
k和tot 又是什么?
求大牛详解RP+++
答
k表示第k堆石头,tot表示分好的第一部分石头的质量
dfs(1,0)表示搜索当分好的第一部分石头质量为0时,第一堆石头的分法