【求助】Pascal石子合并问题.Description 你有N堆石头质量分别为W1,W2,W3...WN.(Wi<=100000)现在需要你将石头合并为两堆,使两堆质量的差的绝对值为最小.Input 第一行为整数N(1=sum)or(k>n) thenbeginans:=m
来源:学生作业帮助网 编辑:作业帮 时间:2024/07/05 03:12:33
![【求助】Pascal石子合并问题.Description 你有N堆石头质量分别为W1,W2,W3...WN.(Wi<=100000)现在需要你将石头合并为两堆,使两堆质量的差的绝对值为最小.Input 第一行为整数N(1=sum)or(k>n) thenbeginans:=m](/uploads/image/z/15259428-36-8.jpg?t=%E3%80%90%E6%B1%82%E5%8A%A9%E3%80%91Pascal%E7%9F%B3%E5%AD%90%E5%90%88%E5%B9%B6%E9%97%AE%E9%A2%98.Description+%E4%BD%A0%E6%9C%89N%E5%A0%86%E7%9F%B3%E5%A4%B4%E8%B4%A8%E9%87%8F%E5%88%86%E5%88%AB%E4%B8%BAW1%2CW2%2CW3...WN.%28Wi%EF%BC%9C%EF%BC%9D100000%29%E7%8E%B0%E5%9C%A8%E9%9C%80%E8%A6%81%E4%BD%A0%E5%B0%86%E7%9F%B3%E5%A4%B4%E5%90%88%E5%B9%B6%E4%B8%BA%E4%B8%A4%E5%A0%86%2C%E4%BD%BF%E4%B8%A4%E5%A0%86%E8%B4%A8%E9%87%8F%E7%9A%84%E5%B7%AE%E7%9A%84%E7%BB%9D%E5%AF%B9%E5%80%BC%E4%B8%BA%E6%9C%80%E5%B0%8F.Input+%E7%AC%AC%E4%B8%80%E8%A1%8C%E4%B8%BA%E6%95%B4%E6%95%B0N%EF%BC%881%3Dsum%29or%28k%3En%29+thenbeginans%3A%3Dm)
【求助】Pascal石子合并问题.Description 你有N堆石头质量分别为W1,W2,W3...WN.(Wi<=100000)现在需要你将石头合并为两堆,使两堆质量的差的绝对值为最小.Input 第一行为整数N(1=sum)or(k>n) thenbeginans:=m
【求助】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分,我不在乎分数.
【求助】Pascal石子合并问题.Description 你有N堆石头质量分别为W1,W2,W3...WN.(Wi<=100000)现在需要你将石头合并为两堆,使两堆质量的差的绝对值为最小.Input 第一行为整数N(1=sum)or(k>n) thenbeginans:=m
这题用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.