第9章 动态规划(背包问题)

PASCAL语言第二部分 基础算法 第九章 动态规划(背包问题)

第九章 动态规划 (背包问题)PASCAL语言—基础算法

PASCAL语言第二部分 基础算法 第九章 动态规划(背包问题)

第一课时

PASCAL语言第二部分 基础算法 第九章 动态规划(背包问题)

上机练习

8、装载问题 【问题描述】 有一批共n个集装箱要装上艘载重量为c的轮船，其中集装 箱i的重量为wi。找出一种最优装载方案，将轮船尽可能装满， 即在装载体积不受限制的情况下，将尽可能重的集装箱装上轮 船。 【输入格式】 由文件load.in给出输入数据。第一行有2个正整数n和c。n 是集装箱数，c是轮船的载重量。接下来的1行中有n个正整数， 表示集装箱的重量。 【输出格式】 将计算出的最大装载重量输出到文件load.out。 【输入样例】 5 10 7 2 6 5 4 【输出样例】 10

PASCAL语言第二部分 基础算法 第九章 动态规划(背包问题)

var n,c,i,max:longint; w:array[1..100000]of integer; procedure search(k,sum:longint); var ii:longint; begin if (sum>max)and(sum<=c) then max:=sum; if k>n then exit else for ii:=0 to 1 do if ii*w[k]+sum<=c then search(k+1,sum+w[k]*ii); end; BEGIN assign(input,'load.in');reset(input); assign(output,'load.out');rewrite(output); read(n,c); for i:=1 to n do read(w[i]); max:=0; search(1,0); writeln(max); CLOSE(INPUT); CLOSE(OUTPUT); END.

PASCAL语言第二部分 基础算法 第九章 动态规划(背包问题)

但是，不论我们怎么用搜索回溯算法 做，都不能得满分。那么用什么算法 做呢？

动态规划！

PASCAL语言第二部分 基础算法 第九章 动态规划(背包问题)

0/1背包

0放

1 不放 先是71 0 2 0 3 0 4 0 5 0

再是27 8 9 /0 / / 0 0 / / / 7 7 7 F[10]:=2+f[10-2] 7 7 9 F[9]:=2+f[9-2] F[8]:=2+f[8-2] 2<7 F[8]不放2 F[7]不放2 F[7]:=2+f[7-2] 2<7 10 / 0 / 7 9

f

0 0

6 0

PASCAL语言第二部分 基础算法 第九章 动态规划(背包问题)

0/1背包

0放

1 不放 再是61 0 2 2 3 2 4 2 5 2

再是57 /7 / 6 7 8 / 7 / 7 7 9 / 9 9/ 9 10 / 9 / 9 9

f

0 0

6 /26

PASCAL语言第二部分 基础算法 第九章 动态规划(背包问题)

0/1背包

0放

1 不放 再是41 0 2 2 3 2 4 2 5 2 6 / 66

f

0 0

7 /77

8 / 77

9 / 9

10 / 9

6+4 6+4

PASCAL语言第二部分 基础算法 第九章 动态规划(背包问题)

【程序】

var n,c,i,j:longint; w,f:array[0..100000]of longint; BEGIN assign(input,'load.in');reset(input); assign(output,'load.out');rewrite(output); read(n,c); ★01背包比回溯算 for i:=1 to n do read(w[i]); for i:=1 to n do 法好得多。 for j:= c downto w[i] do if f[j]<w[i]+f[j-w[i]] then ★1、时间少 f[j]:=w[i]+f[j-w[i]]; writeln(f[c]); ★2、程序短 CLOSE(INPUT); CLOSE(OUTPUT); END.

PASCAL语言第二部分 基础算法 第九章 动态规划(背包问题)

前后对比

var n,c,i,max:longint; w:array[1..100000]of integer; procedure search(k,sum:longint); var ii:longint; begin if (sum>max)and(sum<=c) then max:=sum; if k>n then exit else for ii:=0 to 1 do if ii*w[k]+sum<=c then

var n,c,i,j:longint; w,f:array[0..100000]of longint; BEGIN assign(input,'load.in');reset (input);

search(k+1,sum+w[k]*ii); end;

assign(output,'load.out');re write(output); read(n,c); for i:=1 to n do read(w[i]); for i:=1 to n do for j:= c downto w[i] do if f[j]<w[i]+f[j-w[i]] then f[j]:

=w[i]+f[j-w[i]]; writeln(f[c]);

PASCAL语言第二部分 基础算法 第九章 动态规划(背包问题)

前后对比

BEGIN assign(input,'load.in');reset (input);

CLOSE(INPUT); CLOSE(OUTPUT); END.

assign(output,'load.out');re write(output); read(n,c); for i:=1 to n do read(w[i]); max:=0; search(1,0); writeln(max); CLOSE(INPUT); CLOSE(OUTPUT); END.

PASCAL语言第二部分 基础算法 第九章 动态规划(背包问题)

前后对比想想看，01背包和回溯算法哪 个好？好在哪儿？公式:F[当前总重]:=w[i]+f[当前总重-w[i]]

PASCAL语言第二部分 基础算法 第九章 动态规划(背包问题)

上机练习

P268 2.装箱问题 有一个箱子容量为v(正整数，小于等于20000), 同时有n个物品p[1]-p[n]。 要求从n个物品中，任取m个装入箱内，使它的剩余 空间最少。 [输入格式] V N N行。分别表示p[i] [输出格式] 箱子的剩余空间

PASCAL语言第二部分 基础算法 第九章 动态规划(背包问题)

上机练习

P268 2.装箱问题 [输入样例]boxes.in 24 6 8 3 12 7 9 7

[输出样例]boxes.out 0

PASCAL语言第二部分 基础算法 第九章 动态规划(背包问题)

上机练习

P268 2.装箱问题 有一个箱子容量为v(正整数，小于等于20000), 同时有n个物品p[1]-p[n]。 要求从n个物品中，任取m个装入箱内，使它的剩余 空间最少。

我们可以先求出至少要用多少空间。那不就成load.pas了吗？

PASCAL语言第二部分 基础算法 第九章 动态规划(背包问题)

Load.pas

var n,c,i,j:longint; w,f:array[0..100000]of longint; BEGIN assign(input,'load.in');reset(input); assign(output,'load.out');rewrite(output); read(n,c); for i:=1 to n do read(w[i]); for i:=1 to n do for j:= c downto w[i] do if f[j]<w[i]+f[j-w[i]] then f[j]:=w[i]+f[j-w[i]]; writeln(f[c]); CLOSE(INPUT); CLOSE(OUTPUT); END.

PASCAL语言第二部分 基础算法 第九章 动态规划(背包问题)

Boxes.pas

var v,n,i,j:longint; w,f:array[0..100000]of longint; begin assign(input,'boxes.in');reset(i nput);

assign(output,'boxes.out');re write(output); readln(v); readln(n); for i:=1 to n do readln(w[i]); for i:=1 to n do

for j:=v downto w[i] do if f[j]<w[i]+f[j-w[i]] then f[j]:=w[i]+f[j-w[i]]; writeln(v-f[v]); close(input); close(output); end.

PASCAL语言第二部分 基础算法 第九章 动态规划(背包问题)

第二课时

PASCAL语言第二部分 基础算法 第九章 动态规划(背包问题)

练习

P268 1.weight.pas

PASCAL语言第二部分 基础算法 第九章 动态规划(背包问题)

f

我只同 桶们算一 排会一个 序想个重 到，量 ， 0 1 2 3 4 5 6 7 8 …………………………………… T F F F F F F F F …………………………………… / / / / / / / / T T T 先输入1 (1g 1个) 输入2 (2g 1个) 已经有一个TRUE 已经有2个TRUE (f[0]),所以，f[0+1] (f[0].f[1]),所以， 变成TRUE f[0+2].f[1+2]变成 TRUE

分析

1000

F/

PASCAL语言第二部分 基础算法 第九章 动态规划(背包问题)

const n=6; b:array[1..6]of longint=(1,2,3,5,10,20); var i,j,k,w,total:longint; p:array[1..6]of longint; f:array[0..1000]of boolean; begin

参考程序

assign(input,'weight.in');reset(INPUT);

for i:=1 to w do if f[i] then inc(total); writeln('Total=',total); close(input); close(output); end.

assign(output,'weight.out');rewrite(ou tput); for

i:=1 to n do read(p[i]); w:=0; f[0]:=true; for i:=1 to n do for j:=1 to p[i] do begin for k:=w downto 0 do if f[k] then f[k+b[i]]:=true; w:=w+b[i]; end;

本文来源：https://www.bwwdw.com/article/l5y4.html