C语言，算法、动态规划：有一个箱子的容量为v（正整数，0<=v<=20000）,同时有n个物品（0<n<=30），

信息学 动态规划 习题~

3.动态规划典型例题与习题

3.1 最长不降子序列
3.2 背包问题
3.3 最短路径

4.3 习题


3.1 最长不降子序列
（1）问题描述
设有由n个不相同的整数组成的数列，记为:
a(1)、a(2)、……、a(n)且a(i)a(j) (ij)
例如3，18，7，14，10，12，23，41，16，24。
若存在i1<i2<i3< … < ie 且有a(i1)<a(i2)< … <a(ie)则称为长度为e的不下降序列。如上例中3，18，23，24就是一个长度为4的不下降序列，同时也有3，7，10，12，16，24长度为6的不下降序列。程序要求，当原数列给出之后，求出最长的不下降序列。
（2）算法分析
根据动态规划的原理，由后往前进行搜索。
1· 对a(n)来说，由于它是最后一个数，所以当从a(n)开始查找时，只存在长度为1的不下降序列；
2· 若从a(n-1)开始查找，则存在下面的两种可能性：
①若a(n-1)<a(n)则存在长度为2的不下降序列a(n-1)，a(n)。
②若a(n-1)>a(n)则存在长度为1的不下降序列a(n-1)或a(n)。
3· 一般若从a(i)开始，此时最长不下降序列应该按下列方法求出:
在a(i+1),a(i+2),…,a(n)中，找出一个比a(i)大的且最长的不下降序列，作为它的后继。

4.用数组b(i),c(i)分别记录点i到n的最长的不降子序列的长度和点i后继接点的编号
(3) 程序如下:（逆推法）

program li1;
const maxn=100;
var a,b,c:array[1..maxn] of integer;
fname:string;
f:text;
n,i,j,max,p:integer;
begin
readln(fname);
assign(f,fname);
reset(f);
readln(f,n);+
for i:=1 to n do
begin
read(f,a[i]);
b[n]:=1;
c[n]:=0;
end;
for i:= n-1 downto 1 do
begin
max:=0;p:=0;
for j:=i+1 to n do
if (a[i]max) then begin max:=b[j];p:=j end;
if p0 then begin b[i]:=b[p]+1;c[i]:=p end
end;
max:=0;p:=0;
for i:=1 to n do
if b[i]>max then begin max:=b[i];p:=i end;
writeln('maxlong=',max);
write('result is:');
while p0 do
begin write(a[p]:5);p:=c[p] end;
end.
3.2 背包问题
背包问题有三种

1.部分背包问题

一个旅行者有一个最多能用m公斤的背包，现在有n种物品，它们的总重量分别是W1，W2，...,Wn,它们的总价值分别为C1,C2,...,Cn.求旅行者能获得最大总价值。

解决问题的方法是贪心算法:将C1/W1,C2/W2,...Cn/Wn,从大到小排序,不停地选择价值与重量比最大的放人背包直到放满为止.

2.0/1背包

一个旅行者有一个最多能用m公斤的背包，现在有n件物品，它们的重量分别是W1，W2，...,Wn,它们的价值分别为C1,C2,...,Cn.若每种物品只有一件求旅行者能获得最大总价值。

分析说明:

显然这个题可用深度优先方法对每件物品进行枚举(选或不选用0,1控制).

程序简单,但是当n的值很大的时候不能满足时间要求，时间复杂度为O（2n）。按递归的思想我们可以把问题分解为子问题,使用递归函数

设 f(i，x)表示前i件物品，总重量不超过x的最优价值

则 f（i，x）=max(f(i－1，x-W[i])+C[i]，f（i－1，x））

f（n，m）即为最优解，边界条件为f（0，x）＝0 ，f(i,0)=0;

动态规划方法(顺推法)程序如下:

程序如下：

program knapsack02;
const maxm=200;maxn=30;
type ar=array[1..maxn] of integer;
var m,n,j,i:integer;
c,w:ar;
f:array[0..maxn,0..maxm] of integer;
function max(x,y:integer):integer;
begin
if x>y then max:=x else max:=y;
end;
begin
readln(m,n);
for i:= 1 to n do
readln(w[i],c[i]);
for i:=1 to m do f(0,i):=0;
for i:=1 to n do f(i,0):=0;

for i:=1 to n do
for j:=1 to m do
begin
if j>=w[i] then f[i,j]:=max(f[i-1,j-w[i]]+c[i],f[i-1,j])
else f[i,j]:=f[i-1,j];
end;
writeln(f[n,m]);
end.

使用二维数组存储各子问题时方便，但当maxm较大时如maxn=2000时不能定义二维数组f,怎么办,其实可以用一维数组,但是上述中j:=1 to m 要改为j:=m downto 1,为什么?请大家自己解决。

3.完全背包问题

一个旅行者有一个最多能用m公斤的背包，现在有n种物品，每件的重量分别是W1，W2，...,Wn,

每件的价值分别为C1,C2,...,Cn.若的每种物品的件数足够多.

求旅行者能获得的最大总价值。

本问题的数学模型如下：

设 f(x)表示重量不超过x公斤的最大价值，

则 f(x）=max{f(x-w[i])+c[i]} 当x>=w[i] 1<=i<=n

程序如下:（顺推法）

program knapsack04;
const maxm=2000;maxn=30;
type ar=array[0..maxn] of integer;
var m,n,j,i,t:integer;
c,w:ar;
f:array[0..maxm] of integer;
begin
readln(m,n);
for i:= 1 to n do
readln(w[i],c[i]);
f(0):=0;
for i:=1 to m do
for j:=1 to n do
begin
if i>=w[j] then t:=f[i-w[j]]+c[j];
if t>f[i] then f[i]:=t
end;
writeln(f[m]);
end.

3.3 最短路径



问题描述：

如图：求v1到v10的最短路径长度及最短路径。



图的邻接矩阵如下：

0 2 5 1 -1 -1 -1 -1 -1 -1
-1 0 -1 -1 12 14 -1 -1 -1 -1
-1 -1 0 -1 6 10 4 -1 -1 -1
-1 -1 -1 0 13 12 11 -1 -1 -1
-1 -1 -1 -1 0 -1 -1 3 9 -1
-1 -1 -1 -1 -1 0 -1 6 5 -1
-1 -1 -1 -1 -1 -1 0 -1 10 -1
-1 -1 -1 -1 -1 -1 -1 0 -1 5
-1 -1 -1 -1 -1 -1 -1 -1 0 2
-1 -1 -1 -1 -1 -1 -1 -1 -1 0

采用逆推法

设f（x）表示点x到v10的最短路径长度

则 f(10)=0

f(x)=min{ f(i)+a[x,i] 当a[x,i]>0 ,x<i<=n}

程序如下：（逆推法）

program lt3;
const n=10;
var
a:array[1..n,1..n] of integer;
b,c:array[1..n] of integer;
fname:string;
f:text;
i,j,x:integer;
begin
readln(fname);
assign(f,fname);
reset(f);
for i:=1 to n do
for j:=1 to n do
read(f,a[i,j]);
close(f);
for i:=1 to n do
b[i]:=maxint;
b[n]:=0;
for i:= n-1 downto 1 do
for j:=n downto i+1 do
if (a[i,j]>0) and (b[j]maxint) and (b[j]+a[i,j]<b[i])
then begin b[i]:=b[j]+a[i,j];c[i]:=j end;
writeln('minlong=',b[1]);
x:=1;
while x0 do
begin
write(x:5);
x:=c[x];
end;
end.

3.4习题

1.若城市路径示意图如下图所示:



图中，每条边上的数字是这段道路的长度。条件：从A地出发，只允许向右或向上走。试寻找一条从A地到B地的最短路径和长度。

2.求一个数列中的连续若干个数和的最大值.

3.资源分配问题:n个资源分配到m个项目上，i项目分配j个资源可获益a[i,j],求最大总效益。
4. 装箱问题

问题描述:有一个箱子容量为V（正整数，0＜＝V＜＝20000），同时有n个物品（0＜n＜＝30，每个物品有一个体积（正整数）。要求n个物品中，任取若干个装入箱内，使箱子的剩余空间为最小。

样例

输入：

24 一个整数，表示箱子容量

6 一个整数，表示有n个物品

8 接下来n行，分别表示这n 个物品的各自体积

3

12

7

9

7

输出：

0 一个整数，表示箱子剩余空间。



或者下载动态规划的教程：
http://hi.baidu.com/111010000000/blog/item/69032531bc099f1deac4af46.html

program Sbag;
const maxn=10;
maxv=100;
var f0,f1:array[1..maxv]of boolean;
box:array[1..maxn]of integer;
v,n,i,j:integer;
begin
read(v,n);
for i:=1 to n do read(box[i]);
fillchar(f0,sizeof(f0),0);
f0[0]:=true;
for i:=1 to n do
begin
f1:=f0;
for j:=box[i] to v do
if f0[j-box[i]] then f1[j]:=true;
f1:=f0;
end;
for i:=v downto 1 do
if f1[i] then
begin
writeln(v-i);
halt
end;
end.

#include<stdio.h>
#define N 30
int xiangzi(int n ,int V ,int a[]) //楼主后面的Vo数组必须放进递归函数里面或定义成全局数组 另外h[n]什么情况？？
{
int minv,t,m=V;
if(n==0)
{
if(a[n]<=V) // V是剩余空间。minv是所生最小空间，是待求变量，而不是已知的 ，不能V<minv 这样用来判断。
minv=V-a[n];
else
minv=V;
}
else
{
t=xiangzi(n-1,V,a);
if(a[n]<=V) //可能a[n]比V大 如果按楼主的程序没判断 那么此时m必定小于0，最后的minv肯定是会小雨0的。应该先判断 排除这种情矿。因此前面定义m的时候可以初始化m=V;
m=xiangzi(n-1,V-a[n],a); /*考虑选择这个物体的情况*/
if(t<m)
minv=t;
else
minv=m;
}
return minv;
}

void main()
{
int V;
int n,i,m,min;
int Vo[N];
printf("箱子的容量V为：");
scanf("%d",&V);
printf("物品的种类数为：");
scanf("%d",&n);
printf("物品的体积分别为：\n");
for(i=0;i<n;i++)
scanf("%d",&Vo[i]); //"%d "改成“%d” d后面的空格去掉。不好意思 我学的c++，c的语法不怎么东， 只是调试出来了，不知道原因，可能语法问题吧。
min=xiangzi(n-1,V,Vo);
printf("%d\n",min); //另外别忘了输出
system("pause");
}
就这样了。。。

---

迁西县18838167255： 装箱问题 - ？
台壮众益： 有一个箱子容量为V(正整数,0 要求n个物品中,任取若干个装入箱内,使箱子的剩余空间为最小.样例输入:24 一个整数,表示箱子容量6 一个整数,表示有n个物品8 接下来n行,分别表示这n 个物品的各自体积312797输出:0 ...

迁西县18838167255： C语言动态规划之背包问题求解 - ？
台壮众益： #include<stdio.h> int max(int a,int b) { if (a>b) return a; else return b; } int main() { //int max(int , int ); int n,m,i,j; int data[101][2]; int f[101][101]; scanf(＂%d%d＂,&n,&m); //n表示个数,m表示能背的最大重量 for(i=1;i<=n;i++) { scanf(＂%d%d＂,&data[...

迁西县18838167255： 背包算法的C#代码 - ？
台壮众益： 背包问题 有一个箱子容量为V,同时有n个物品,每个物品有一个体积(正整数).设计一个算法在n个物品中,任取若干个装入箱内,使箱子的剩余空间为最小.动态规划 C#版算法//体积表:当不同的参照物时,在各种体积箱子下,最大的占用...

迁西县18838167255： 分别用回溯法和动态规划求0/1背包问题(C语言代码) - ？
台壮众益： #include <stdio.h> #include <malloc.h> #include <windows.h> typedef struct goods { double *value; //价值 double *weight; //重量 char *select; //是否选中到方案 int num;//物品数量 double limitw; //限制重量 }GOODS; double maxvalue,...

迁西县18838167255： c语言动态规划的一个问题 - ？
台壮众益： 动态规划关键是找到问题中的子问题,写出状态方程. 这个问题的子问题可以定义为前n件物品,总费用为v的最大价值总和. 先考虑第n件物品,如果c[n]f(n,v)=max{f(n-1,v-c[n]*i)+w[n]*i};i根据物品费用和对应的总费用确定取值,即小于对应的总费用时可取0,1,否则为0. 很明显最简单的是从前1件物品中选取,这个就是最后用递归程序编写程序时候的出口. 算法思想就是上面所写的.程序的精华在于思想,仅供你编程参考.

迁西县18838167255： 用动态规划法解 0/1背包问题 要求用c语言编写程序原代码. - ？
台壮众益： 1.动态规划 #include<stdio.h>#include<stdlib.h>#include<time.h> #define N 100 //货物的种类#define M 10 //货物的质量(千克) typedef struct good { int no; //第几个物品 int w; //质量 int p; //可获利 int flag; float pw; //获得的最高利润 }Good; ...

迁西县18838167255： c语言01背包问题谁能简单说下？
台壮众益： 01背包问题就是有个容量为W的包,然后有一堆的物品(1...n),其中wi、vi分别为第i个物品的重量和价值,现在需要求的就是使得包中所装的物品尽可能的价值高.那么这个物品放不放在包中对应取值0 or 1.其算法为动态规划,需要证明最...

迁西县18838167255： 求动态规划0 - 1背包算法解释 - ？
台壮众益： 01背包问题 题目 有N件物品和一个容量为V的背包.第i件物品的费用是c[i],价值是w[i].求解将哪些物品装入背包可使价值总和最大.基本思路 这是最基础的背包问题,特点是:每种物品仅有一件,可以选择放或不放.用子问题定义状态:即...

迁西县18838167255： 用C语言编的推箱子游戏的流程图在哪能找到? - ？
台壮众益： include＂stdio.h＂#include＂bios.h＂#define LEFT 75#define RIGHT 77#define UPPER 72#define DOWN 80#define ESC 27 struct Boxss /*定义箱子结构体,其中包含坐标属性*/ { int x,y;};union keyboard /*定义读取键盘码的共用体类型*/ { ...

迁西县18838167255： C语言动规问题？
台壮众益： #include<stdio.h>//滑雪、、搜索+动态规划 #define max(a,b) a>b?a:b int m,n; int map[105][105]; int step[105][105];//动态规划出最大的step-length bool hash[105][105];//标记是否被走过 int dir[4][2]={-1,0,1,0,0,1,0,-1};//四个方向 int bfs(int x,int y)/...