作业帮【求助】Pascal石子合并问题.
来源：学生作业帮 编辑：作业帮 分类：综合作业 时间：2024/11/08 06:36:29
【求助】Pascal石子合并问题.
Description
你有N堆石头质量分别为W1,W2,W3...WN.(Wi＜＝100000)现在需要你将石头合并为两堆,使两堆质量的差的绝对值为最小.
Input
第一行为整数N（1=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;
sum:=0;
read(n);
for i:=1 to n do
begin
read(w[i]);
sum:=sum+w[i];
end;
dfs(1,0);
writeln(ans);
end.
初学者,最好“每行代码”都给个解释啊!
如果有不同看法的也可以,帮我把代码写出来然后给个解释啊!
好的+100分,我不在乎分数.
Description
你有N堆石头质量分别为W1,W2,W3...WN.(Wi＜＝100000)现在需要你将石头合并为两堆,使两堆质量的差的绝对值为最小.
Input
第一行为整数N（1=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;
sum:=0;
read(n);
for i:=1 to n do
begin
read(w[i]);
sum:=sum+w[i];
end;
dfs(1,0);
writeln(ans);
end.
初学者,最好“每行代码”都给个解释啊!
如果有不同看法的也可以,帮我把代码写出来然后给个解释啊!
好的+100分,我不在乎分数.
这题用DP很简单, 想回溯 那就回溯吧
首先先清楚DFS, 没个石子有两种可能 取或不取
然后进行下一个
比如 2 3
DFS(1,TOT+2) 就是2取了 然后继续对下一个DFS
DFS(1,TOT) 就是2不取 然后继续下一个DFS
program shizihebing;
var
ans,sum,i,j,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 如果(TOT超过 sum/2 那么没必要再去下去了,因为这个答案一定比接下去的答案更优 例如 2 4 5 取了2 4 超过了(2+4+5)/2 还有必要再取5吗? (2+4)-5,(2+4+5) 仔细想想,此步为剪枝,)(k>n 边界条件退出)
begin
ans:=min(ans,abs(sum-tot-tot));
exit;
end;
dfs(k+1,tot+w[k]); (取)
dfs(k+1,tot); (不取)
end;
begin
ans:=maxlongint;
sum:=0;
read(n);
for i:=1 to n do
begin
read(w[i]);
sum:=sum+w[i];
end;
dfs(1,0);(从第一个开始取)
writeln(ans);
end.
再问： ans:=min(ans,abs(sum-tot-tot)); 什么意思啊 还有K有什么用，Tot有什么用。
首先先清楚DFS, 没个石子有两种可能 取或不取
然后进行下一个
比如 2 3
DFS(1,TOT+2) 就是2取了 然后继续对下一个DFS
DFS(1,TOT) 就是2不取 然后继续下一个DFS
program shizihebing;
var
ans,sum,i,j,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 如果(TOT超过 sum/2 那么没必要再去下去了,因为这个答案一定比接下去的答案更优 例如 2 4 5 取了2 4 超过了(2+4+5)/2 还有必要再取5吗? (2+4)-5,(2+4+5) 仔细想想,此步为剪枝,)(k>n 边界条件退出)
begin
ans:=min(ans,abs(sum-tot-tot));
exit;
end;
dfs(k+1,tot+w[k]); (取)
dfs(k+1,tot); (不取)
end;
begin
ans:=maxlongint;
sum:=0;
read(n);
for i:=1 to n do
begin
read(w[i]);
sum:=sum+w[i];
end;
dfs(1,0);(从第一个开始取)
writeln(ans);
end.
再问： ans:=min(ans,abs(sum-tot-tot)); 什么意思啊 还有K有什么用，Tot有什么用。