动态规划中的0-1背包问题怎么去理解?要求给出具体实例和详细步骤。。。
一.动态规划求解0-1背包问题
/************************************************************************/
/* 0-1背包问题:
/* 给定n种物品和一个背包
/* 物品i的重量为wi,其价值为vi
/* 背包的容量为c
/* 应如何选择装入背包的物品,使得装入背包中的物品
/* 的总价值最大?
/* 注:在选择装入背包的物品时,对物品i只有两种选择,
/* 即装入或不装入背包。不能将物品i装入多次,也
/* 不能只装入部分的物品i。
/*
/* 1. 0-1背包问题的形式化描述:
/* 给定c>0, wi>0, vi>0, 0<=i<=n,要求找到一个n元的
/* 0-1向量(x1, x2, ..., xn), 使得:
/* max sum_{i=1 to n} (vi*xi),且满足如下约束:
/* (1) sum_{i=1 to n} (wi*xi) <= c
/* (2) xi∈{0, 1}, 1<=i<=n
/*
/* 2. 0-1背包问题的求解
/* 0-1背包问题具有最优子结构性质和子问题重叠性质,适于
/* 采用动态规划方法求解
/*
/* 2.1 最优子结构性质
/* 设(y1,y2,...,yn)是给定0-1背包问题的一个最优解,则必有
/* 结论,(y2,y3,...,yn)是如下子问题的一个最优解:
/* max sum_{i=2 to n} (vi*xi)
/* (1) sum_{i=2 to n} (wi*xi) <= c - w1*y1
/* (2) xi∈{0, 1}, 2<=i<=n
/* 因为如若不然,则该子问题存在一个最优解(z2,z3,...,zn),
/* 而(y2,y3,...,yn)不是其最优解。那么有:
/* sum_{i=2 to n} (vi*zi) > sum_{i=2 to n} (vi*yi)
/* 且,w1*y1 + sum_{i=2 to n} (wi*zi) <= c
/* 进一步有:
/* v1*y1 + sum_{i=2 to n} (vi*zi) > sum_{i=1 to n} (vi*yi)
/* w1*y1 + sum_{i=2 to n} (wi*zi) <= c
/* 这说明:(y1,z2,z3,...zn)是所给0-1背包问题的更优解,那么
/* 说明(y1,y2,...,yn)不是问题的最优解,与前提矛盾,所以最优
/* 子结构性质成立。
/*
/* 2.2 子问题重叠性质
/* 设所给0-1背包问题的子问题 P(i,j)为:
/* max sum_{k=i to n} (vk*xk)
/* (1) sum_{k=i to n} (wk*xk) <= j
/* (2) xk∈{0, 1}, i<=k<=n
/* 问题P(i,j)是背包容量为j、可选物品为i,i+1,...,n时的子问题
/* 设m(i,j)是子问题P(i,j)的最优值,即最大总价值。则根据最优
/* 子结构性质,可以建立m(i,j)的递归式:
/* a. 递归初始 m(n,j)
/* //背包容量为j、可选物品只有n,若背包容量j大于物品n的
/* //重量,则直接装入;否则无法装入。
/* m(n,j) = vn, j>=wn
/* m(n,j) = 0, 0<=j<wn
/* b. 递归式 m(i,j)
/* //背包容量为j、可选物品为i,i+1,...,n
/* //如果背包容量j<wi,则根本装不进物品i,所以有:
/* m(i,j) = m(i+1,j), 0<=j<wi
/* //如果j>=wi,则在不装物品i和装入物品i之间做出选择
/* 不装物品i的最优值:m(i+1,j)
/* 装入物品i的最优值:m(i+1, j-wi) + vi
/* 所以:
/* m(i,j) = max {m(i+1,j), m(i+1, j-wi) + vi}, j>=wi
/*
/************************************************************************/
#define max(a,b) (((a) > (b)) ? (a) : (b))
#define min(a,b) (((a) < (b)) ? (a) : (b))
template
void Knapsack(Type* v, int *w, int c, int n, Type **m)
{
//递归初始条件
int jMax = min(w[n] - 1, c);
for (int j=0; j<=jMax; j++) {
m[n][j] = 0;
}
for (j=w[n]; j<=c; j++) {
m[n][j] = v[n];
}
//i从2到n-1,分别对j>=wi和0<=j<wi即使m(i,j)
for (int i=n-1; i>1; i--) {
jMax = min(w[i] - 1, c);
for (int j=0; j<=jMax; j++) {
m[i][j] = m[i+1][j];
}
for (j=w[i]; j<=c; j++) {
m[i][j] = max(m[i+1][j], m[i+1][j-w[i]]+v[i]);
}
}
m[1][c] = m[2][c];
if (c >= w[1]) {
m[1][c] = max(m[1][c], m[2][c-w[1]]+v[1]);
}
}
template
void TraceBack(Type **m, int *w, int c, int n, int* x)
{
for (int i=1; i<n; i++) {
if(m[i][c] == m[i+1][c]) x[i] = 0;
else {
x[i] = 1;
c -= w[i];
}
}
x[n] = (m[n][c])? 1:0;
}
int main(int argc, char* argv[])
{
int n = 5;
int w[6] = {-1, 2, 2, 6, 5, 4};
int v[6] = {-1, 6, 3, 5, 4, 6};
int c = 10;
int **ppm = new int*[n+1];
for (int i=0; i<n+1; i++) {
ppm[i] = new int[c+1];
}
int x[6];
Knapsack(v, w, c, n, ppm);
TraceBack(ppm, w, c, n, x);
return 0;
}
二.贪心算法求解0-1背包问题
1.贪心法的基本思路:
——从问题的某一个初始解出发逐步逼近给定的目标,以尽可能快的地求得更好的解。当达到某算法中的某一步不能再继续前进时,算法停止。
该算法存在问题:
1).不能保证求得的最后解是最佳的;
2).不能用来求最大或最小解问题;
3).只能求满足某些约束条件的可行解的范围。
实现该算法的过程:
从问题的某一初始解出发;
while 能朝给定总目标前进一步 do
求出可行解的一个解元素;
由所有解元素组合成问题的一个可行解;
2.例题分析
1).[背包问题]有一个背包,背包容量是M=150。有7个物品,物品可以分割成任意大小。
要求尽可能让装入背包中的物品总价值最大,但不能超过总容量。
物品 A B C D E F G
重量 35 30 60 50 40 10 25
价值 10 40 30 50 35 40 30
分析:
目标函数: ∑pi最大
约束条件是装入的物品总重量不超过背包容量:∑wi<=M( M=150)
(1)根据贪心的策略,每次挑选价值最大的物品装入背包,得到的结果是否最优?
(2)每次挑选所占空间最小的物品装入是否能得到最优解?
(3)每次选取单位容量价值最大的物品,成为解本题的策略。
(环境:c++)
#include
#define max 100 //最多物品数
void sort (int n,float a[max],float b[max]) //按价值密度排序
{
int j,h,k;
float t1,t2,t3,c[max];
for(k=1;k<=n;k++)
c[k]=a[k]/b[k];
for(h=1;h<n;h++)
for(j=1;j<=n-h;j++)
if(c[j]<c[j+1])
{t1=a[j];a[j]=a[j+1];a[j+1]=t1;
t2=b[j];b[j]=b[j+1];b[j+1]=t2;
t3=c[j];c[j]=c[j+1];c[j+1]=t3;
}
}
void knapsack(int n,float limitw,float v[max],float w[max],int x[max])
{float c1; //c1为背包剩余可装载重量
int i;
sort(n,v,w); //物品按价值密度排序
c1=limitw;
for(i=1;i<=n;i++)
{
if(w[i]>c1)break;
x[i]=1; //x[i]为1时,物品i在解中
c1=c1-w[i];
}
}
void main()
{int n,i,x[max];
float v[max],w[max],totalv=0,totalw=0,limitw;
cout<<"请输入n和limitw:";
cin>>n >>limitw;
for(i=1;i<=n;i++)
x[i]=0; //物品选择情况表初始化为0
cout<<"请依次输入物品的价值:"<<endl;
for(i=1;i<=n;i++)
cin>>v[i];
cout<<endl;
cout<<"请依次输入物品的重量:"<<endl;
for(i=1;i<=n;i++)
cin>>w[i];
cout<<endl;
knapsack (n,limitw,v,w,x);
cout<<"the selection is:";
for(i=1;i<=n;i++)
{
cout<<x[i];
if(x[i]==1)
totalw=totalw+w[i];
}
cout<<endl;
cout<<"背包的总重量为:"<<totalw<<endl; //背包所装载总重量
cout<<"背包的总价值为:"<<totalv<<endl; //背包的总价值
}
三.回溯算法求解0-1背包问题
1.0-l背包问题是子集选取问题。
一般情况下,0-1背包问题是NP难题。0-1背包
问题的解空间可用子集树表示。解0-1背包问题的回溯法与装载问题的回溯法十分类
似。在搜索解空间树时,只要其左儿子结点是一个可行结点,搜索就进入其左子树。当
右子树有可能包含最优解时才进入右子树搜索。否则将右子树剪去。设r是当前剩余
物品价值总和;cp是当前价值;bestp是当前最优价值。当cp+r≤bestp时,可剪去右
子树。计算右子树中解的上界的更好方法是将剩余物品依其单位重量价值排序,然后
依次装入物品,直至装不下时,再装入该物品的一部分而装满背包。由此得到的价值是
右子树中解的上界。
2.解决办法思路:
为了便于计算上界,可先将物品依其单位重量价值从大到小排序,此后只要顺序考
察各物品即可。在实现时,由bound计算当前结点处的上界。在搜索解空间树时,只要其左儿子节点是一个可行结点,搜索就进入左子树,在右子树中有可能包含最优解是才进入右子树搜索。否则将右子树剪去。
回溯法是一个既带有系统性又带有跳跃性的的搜索算法。它在包含问题的所有解的解空间树中,按照深度优先的策略,从根结点出发搜索解空间树。算法搜索至解空间树的任一结点时,总是先判断该结点是否肯定不包含问题的解。如果肯定不包含,则跳过对以该结点为根的子树的系统搜索,逐层向其祖先结点回溯。否则,进入该子树,继续按深度优先的策略进行搜索。回溯法在用来求问题的所有解时,要回溯到根,且根结点的所有子树都已被搜索遍才结束。而回溯法在用来求问题的任一解时,只要搜索到问题的一个解就可以结束。这种以深度优先的方式系统地搜索问题的解的算法称为回溯法,它适用于解一些组合数较大的问题。
2.算法框架:
a.问题的解空间:应用回溯法解问题时,首先应明确定义问题的解空间。问题的解空间应到少包含问题的一个(最优)解。
b.回溯法的基本思想:确定了解空间的组织结构后,回溯法就从开始结点(根结点)出发,以深度优先的方式搜索整个解空间。这个开始结点就成为一个活结点,同时也成为当前的扩展结点。在当前的扩展结点处,搜索向纵深方向移至一个新结点。这个新结点就成为一个新的活结点,并成为当前扩展结点。如果在当前的扩展结点处不能再向纵深方向移动,则当前扩展结点就成为死结点。换句话说,这个结点不再是一个活结点。此时,应往回移动(回溯)至最近的一个活结点处,并使这个活结点成为当前的扩展结点。回溯法即以这种工作方式递归地在解空间中搜索,直至找到所要求的解或解空间中已没有活结点时为止。
3.运用回溯法解题通常包含以下三个步骤:
a.针对所给问题,定义问题的解空间;
b.确定易于搜索的解空间结构;
c.以深度优先的方式搜索解空间,并且在搜索过程中用剪枝函数避免无效搜索;
#include
using namespace std;
class Knap
{
friend int Knapsack(int p[],int w[],int c,int n );
public:
void print()
{
for(int m=1;m<=n;m++)
{
cout<<bestx[m]<<" ";
}
cout<<endl;
};
private:
int Bound(int i);
void Backtrack(int i);
int c;//背包容量
int n; //物品数
int *w;//物品重量数组
int *p;//物品价值数组
int cw;//当前重量
int cp;//当前价值
int bestp;//当前最优值
int *bestx;//当前最优解
int *x;//当前解
};
int Knap::Bound(int i)
{
//计算上界
int cleft=c-cw;//剩余容量
int b=cp;
//以物品单位重量价值递减序装入物品
while(i<=n&&w[i]<=cleft)
{
cleft-=w[i];
b+=p[i];
i++;
}
//装满背包
if(i<=n)
b+=p[i]/w[i]*cleft;
return b;
}
void Knap::Backtrack(int i)
{
if(i>n)
{
if(bestp<cp)
{
for(int j=1;j<=n;j++)
bestx[j]=x[j];
bestp=cp;
}
return;
}
if(cw+w[i]<=c) //搜索左子树
{
x[i]=1;
cw+=w[i];
cp+=p[i];
Backtrack(i+1);
cw-=w[i];
cp-=p[i];
}
if(Bound(i+1)>bestp)//搜索右子树
{
x[i]=0;
Backtrack(i+1);
}
}
class Object
{
friend int Knapsack(int p[],int w[],int c,int n);
public:
int operator<=(Object a)const
{
return (d>=a.d);
}
private:
int ID;
float d;
};
int Knapsack(int p[],int w[],int c,int n)
{
//为Knap::Backtrack初始化
int W=0;
int P=0;
int i=1;
Object *Q=new Object[n];
for(i=1;i<=n;i++)
{
Q[i-1].ID=i;
Q[i-1].d=1.0*p[i]/w[i];
P+=p[i];
W+=w[i];
}
if(W<=c)
return P;//装入所有物品
//依物品单位重量排序
float f;
for( i=0;i<n;i++)
for(int j=i;j<n;j++)
{
if(Q[i].d<Q[j].d)
{
f=Q[i].d;
Q[i].d=Q[j].d;
Q[j].d=f;
}
}
Knap K;
K.p = new int[n+1];
K.w = new int[n+1];
K.x = new int[n+1];
K.bestx = new int[n+1];
K.x[0]=0;
K.bestx[0]=0;
for( i=1;i<=n;i++)
{
K.p[i]=p[Q[i-1].ID];
K.w[i]=w[Q[i-1].ID];
}
K.cp=0;
K.cw=0;
K.c=c;
K.n=n;
K.bestp=0;
//回溯搜索
K.Backtrack(1);
K.print();
delete [] Q;
delete [] K.w;
delete [] K.p;
return K.bestp;
}
void main()
{
int *p;
int *w;
int c=0;
int n=0;
int i=0;
char k;
cout<<"0-1背包问题——回溯法 "<<endl;
cout<<" by zbqplayer "<<endl;
while(k)
{
cout<<"请输入背包容量(c):"<<endl;
cin>>c;
cout<<"请输入物品的个数(n):"<<endl;
cin>>n;
p=new int[n+1];
w=new int[n+1];
p[0]=0;
w[0]=0;
cout<<"请输入物品的价值(p):"<<endl;
for(i=1;i<=n;i++)
cin>>p[i];
cout<<"请输入物品的重量(w):"<<endl;
for(i=1;i<=n;i++)
cin>>w[i];
cout<<"最优解为(bestx):"<<endl;
cout<<"最优值为(bestp):"<<endl;
cout<<Knapsack(p,w,c,n)<<endl;
cout<<"[s] 重新开始"<<endl;
cout<<"[q] 退出"<<endl;
cin>>k;
}
四.分支限界法求解0-1背包问题
1.问题描述:已知有N个物品和一个可以容纳M重量的背包,每种物品I的重量为WEIGHT,一个只能全放入或者不放入,求解如何放入物品,可以使背包里的物品的总效益最大。
2.设计思想与分析:对物品的选取与否构成一棵解树,左子树表示不装入,右表示装入,通过检索问题的解树得出最优解,并用结点上界杀死不符合要求的结点。
#include
struct good
{
int weight;
int benefit;
int flag;//是否可以装入标记
};
int number=0;//物品数量
int upbound=0;
int curp=0, curw=0;//当前效益值与重量
int maxweight=0;
good *bag=NULL;
void Init_good()
{
bag=new good [number];
for(int i=0; i<number; i++)
{
cout<<"请输入第件"<<i+1<<"物品的重量:";
cin>>bag[i].weight;
cout<<"请输入第件"<<i+1<<"物品的效益:";
cin>>bag[i].benefit;
bag[i].flag=0;//初始标志为不装入背包
cout<<endl;
}
}
int getbound(int num, int *bound_u)//返回本结点的c限界和u限界
{
for(int w=curw, p=curp; num<number && (w+bag[num].weight)<=maxweight; num++)
{
w=w+bag[num].weight;
p=w+bag[num].benefit;
}
*bound_u=p+bag[num].benefit;
return ( p+bag[num].benefit*((maxweight-w)/bag[num].weight) );
}
void LCbag()
{
int bound_u=0, bound_c=0;//当前结点的c限界和u限界
for(int i=0; i<number; i++)//逐层遍历解树决定是否装入各个物品
{
if( ( bound_c=getbound(i+1, &bound_u) )>upbound )//遍历左子树
upbound=bound_u;//更改已有u限界,不更改标志
if( getbound(i, &bound_u)>bound_c )//遍历右子树
//若装入,判断右子树的c限界是否大于左子树根的c限界,是则装入
{
upbound=bound_u;//更改已有u限界
curp=curp+bag[i].benefit;
curw=curw+bag[i].weight;//从已有重量和效益加上新物品
bag[i].flag=1;//标记为装入
}
}
}
void Display()
{
cout<<"可以放入背包的物品的编号为:";
for(int i=0; i<number; i++)
if(bag[i].flag>0)
cout<<i+1<<" ";
cout<<endl;
delete []bag;
}
这是清华算法设计C++描述上的代码吧?呵呵 我正巧读过。
简单解释一下吧 在解释之前你要知道动态规划是一个自底向上的过程
这个算法用到了一个二维数组m[][] 来存储各个坐标的价值信息 所以横坐标表示背包号码 纵坐标表示背包容量从1到c
注意该算法只能限制c是整数且每个背包的重量也是整数.
然后int jMax=min(w[n]-1,c);找出w[n]-1和 c之间的小者。
for(int j=0;j<=jMax;j++) m[n][j]=0;表示第n个物品不选 那么所以价值为0
for(int j=w[n];j<=c;j++) m[n][j]=v[n];表示第n个物品选择 所以价值为v[n]
for(int i=n-1;i>1;i--){
jMax=min(w[i]-1,c);
for(int j=0;j<=jMax;j++) m[i][j]=m[i+1][j];
for(int j=w[i];j<=c;j++) m[i][j]=max(m[i+1][j],m[i+1][j-w[i]]+v[i]);
}
表示自n-1到2逐层计算各m[i][j]的值 每一个m[i][j]的值都是根据上一层也就是m[i][j+1] 得到的 最后处理个第一层的边界条件 m[1][c]就是所得答案了
它们的重量分别是W1,W2,...,Wn,
它们的价值分别为P1,P2,...,Pn.
若每种物品只有一件求旅行者能获得最大总价值。
输入格式:
M,N
W1,P1
W2,P2
......
输出格式:
X
*/
因为背包最大容量M未知。所以,我们的程序要从1到M一个一个的试。比如,开始任选N件物品的一个。看对应M的背包,能不能放进去,如果能放进去,并且还有多的空间,则,多出来的空间里能放N-1物品中的最大价值。怎么能保证总选择是最大价值呢?看下表。
测试数据:
10,3
3,4
4,5
5,6
c[i][j]数组保存了1,2,3号物品依次选择后的最大价值.
这个最大价值是怎么得来的呢?从背包容量为0开始,1号物品先试,0,1,2,的容量都不能放.所以置0,背包容量为3则里面放4.这样,这一排背包容量为4,5,6,....10的时候,最佳方案都是放4.假如1号物品放入背包.则再看2号物品.当背包容量为3的时候,最佳方案还是上一排的最价方案c为4.而背包容量为5的时候,则最佳方案为自己的重量5.背包容量为7的时候,很显然是5加上一个值了。加谁??很显然是7-4=3的时候.上一排 c3的最佳方案是4.所以。总的最佳方案是5+4为9.这样.一排一排推下去。最右下放的数据就是最大的价值了。(注意第3排的背包容量为7的时候,最佳方案不是本身的6.而是上一排的9.说明这时候3号物品没有被选.选的是1,2号物品.所以得9.)
从以上最大价值的构造过程中可以看出。
f(n,m)=max{f(n-1,m), f(n-1,m-w[n])+P(n,m)}这就是书本上写的动态规划方程.这回清楚了吗?
下面是实际程序:
#include<stdio.h>
int c[10][100];/*对应每种情况的最大价值*/
int knapsack(int m,int n)
{
int i,j,w[10],p[10];
for(i=1;i<n+1;i++)
scanf("\n%d,%d",&w[i],&p[i]);
for(i=0;i<10;i++)
for(j=0;j<100;j++)
c[i][j]=0;/*初始化数组*/
for(i=1;i<n+1;i++)
for(j=1;j<m+1;j++)
{
if(w[i]<=j) /*如果当前物品的容量小于背包容量*/
{
if(p[i]+c[i-1][j-w[i]]>c[i-1][j])
/*如果本物品的价值加上背包剩下的空间能放的物品的价值*/
/*大于上一次选择的最佳方案则更新c[i][j]*/
c[i][j]=p[i]+c[i-1][j-w[i]];
else
c[i][j]=c[i-1][j];
}
else c[i][j]=c[i-1][j];
}
return(c[n][m]);
}
int main()
{
int m,n;int i,j;
scanf("%d,%d",&m,&n);
printf("Input each one:\n");
printf("%d",knapsack(m,n));
printf("\n");/*下面是测试这个数组,可删除*/
for(i=0;i<10;i++)
for(j=0;j<15;j++)
{
printf("%d ",c[i][j]);
if(j==14)printf("\n");
}
system("pause");
}
引用一个朋友的博文回答你的问题。
Description
试设计一个用回溯法搜索子集空间树的函数。该函数的参数包括结点可行性判定函数和
上界函数等必要的函数,并将此函数用于解0-1背包问题。
0-1 背包问题描述如下:给定n 种物品和一个背包。物品i 的重量是 wi ,其价值为 vi ,
背包的容量为C。应如何选择装入背包的物品,使得装入背包中物品的总价值最大?
在选择装入背包的物品时,对每种物品i只有2 种选择,即装入背包或不装入背包。不能
将物品i 装入背包多次,也不能只装入部分的物品i。
Input
由文件input.txt给出输入数据。第一行有2个正整数n和c。n是物品数,c是背包的容
量。接下来的1 行中有n个正整数,表示物品的价值。第3 行中有n个正整数,表示物品的
重量。
Output
将计算出的装入背包物品的最大价值和最优装入方案输出到文件output.txt。
Sample Input
5 10
6 3 5 4 6
2 2 6 5 4
Sample Output
15
1 1 0 0 1
Source
//code c++
#include <iostream.h>
#include<iomanip.h>
#include<string.h>
int min(int w,int c)
{int temp;<br/> if (w<c) temp=w;<br/> else<br/> temp=c;<br/> return temp;<br/>}
int max(int w,int c)
{
int temp;
if (w>c) temp=w;
else
temp=c;
return temp;
}
void knapsack(int v[],int w[],int c,int n,int**m) //求最优值
{
int jmax=min(w[n]-1,c);
for(int j=0;j<=jmax;j++)
m[n][j]=0;
for(int jj=w[n];jj<=c;jj++)
m[n][jj]=v[n];
for(int i=n-1;i>1;i--){
jmax=min(w[i]-1,c);
for(int j=0;j<=jmax;j++)
m[i][j]=m[i+1][j];
for(int jj=w[i];jj<=c;jj++)
m[i][jj]=max(m[i+1][jj],m[i+1][jj-w[i]]+v[i]);
}
m[1][c]=m[2][c];
if(c>=w[1])
m[1][c]=max(m[1][c],m[2][c-w[1]]+v[1]);
cout<<m[1][c]<<endl;
}
int traceback(int **m,int w[],int c,int n,int x[]) //回代,求最优解
{
//cout<<"得到的一组最优解如下:"<<endl;
for(int i=1;i<n;i++)
if(m[i][c]==m[i+1][c]) x[i]=0;
else {x[i]=1;<br/> c-=w[i];}
x[n]=(m[n][c])?1:0;
for(int y=1;y<=n;y++)
{
cout<<x[y]<<" ";
}
cout<<endl;
return x[n];
}
int main()
{
int n,c;
int **m;
cin>>n>>c;
int *v=new int[n+1];
for(int i=1;i<=n;i++)
cin>>v[i];
int *w=new int[n+1];
for(int j=1;j<=n;j++)
cin>>w[j];
int *x=new int[n+1];
m=new int*[n+1]; //动态的分配二维数组
for(int p=0;p<n+1;p++)
{
m[p]=new int[c+1];
}
knapsack(v,w,c,n,m);
traceback(m,w,c,n,x);
delete []x;
delete []w;
delete []v;
return 0;
}
dp动态规划中的背包问题01
那么f[N][V]必然没有意义了。只能去找f[N][0..V]中的最大值来输出。但是如果我们改变一下f[i][v]的定义:用前i种物品,在总重不超过v的情况下,最大价值是多少。就可以直接输出f[N][V]了,这样只需要改变一下转移方程,加上一项f[i][v-1]。还有问题请追问。
动态规划如何去找动态转移方程?
0 3 9 2 8 5 5 7 0 样例输出 Sample Output 34 【问题分析】这个题目要求我们在一个给定的矩阵中选择不相交的两条路径(首尾除外,而且必须相交),使得路径上的所有数和最大。【算法描述】这类题目有两种做法,一种是动态规划,一种是最小费流。由于最小费流实现比较复杂,没有什么实际意义,...
动态规划分配礼物问题
思想:1:对礼物的价值排序,采用快速排序,从价值大到小排序。2:主体思想:2.1初始化:把第一个礼物分给Alan, 第二个礼物分给Bob,并以a、b纪录2者的个人的总价值 2.2:循环以下动作,直到分配结束:if a<=b,把下一个礼物分给Alan else ,把下一个礼物分给Bob 复杂度:排序复杂度为O(...
一般数学规划模型的动态规划解法中约束条件的个数多余1个时怎么计算
转化一下,要么转化到目标函数里,要么转化到1个约束。
c语言的动态规划算法的这道题怎么做啊,求大神!!!
2. dp[i][0],1<=i<=n,表示只选择竞赛题型 0..i-1 并且竞赛总时间为 0 时最多得分,显然等于0。3. dp[i][j],1<=i<=n,1<=j<=m,表示最多只选择竞赛题型 0..i-1 并且竞赛总时间为 j 时最多得分。3.1 如果不选择第 i-1 种题型,则最多得分 dp[i][j] = dp[i-1]...
【JS算法】动态规划 - 斐波那契数列
其基本思想也是将待求解问题分解成若干个子问题,先求解子问题,然后从这些子问题的解得到原问题的解。 与分治法不同,适合于用动态规划求解的问题,经分解得到子问题往往不是互相独立。即下一个子阶段的求解是建立在上一个子阶段的解的基础上,进行进一步的求解。[0,1,1,2,3,5,8,13...]递...
C语言 动态规划 完全装箱问题
为此,对装箱问题采用非常简单的近似算法,即贪婪法。该算法依次将物品放到它第一个能放进去的箱子中,该算法虽不能保证找到最优解,但还是能找到非常好的解。不失一般性,设n件物品的体积是按从大到小排好序的,即有v0≥v1≥…≥vn-1。如不满足上述要求,只要先对这n件物品按它们的体积从大到...
使用动态规划方法,设计一个将X兑换成相同数额硬币且使用最少硬币的方法...
先说一下解题的思路。动态规划的思想这里不多说了,网上资料很多。针对这个问题,我使用如下公式进行求解:f(n) = min(f(n - 50), f(n - 30, f(n - 8), f(n - 5), f(n - 1)) + 1;f(n) = 0 when n = 0;f(n) = invalid when n < 0;也就是说,对于任意一个给定...
树形动态规划建树的思路与pascal的代码???求助啊求助~~~谢谢啊谢谢...
标程中节点-1表示空节点,0是根节点,1—n是n门可选课程的节点. 思考:若本题加上选那些课程可得到这个最大学分,怎样修改程序? 实现: 怎么实现,是在竞赛中的很重要的一个问题,如果你想ac了这道题目的话,你应该熟悉怎么把一棵树转化成二叉树,完后怎么用递规的思想来实现动态规划。所以坚实的基础是很重要的...
动态规划资源分配问题
f[i,j]表示前i万元投资j个工厂的最大总利润增长,a[i,j]为图表中数据,则f[i,j]=max{f[i,j],f[i-1,k]+a[i,j-k]}(0<=k<=j)
包沫复方: 注意到原来每次f[i][v]只用了一次,所以现在f[v]相当于原来的f[v], 上次循环保存的f[v]相当于原来的f[i-1][v] 如果从0做到V的话,没有重复限制,会从v->v+c[i]->v+2*c[i]加上去,本次循环的c[i]也会加上
湛河区15576592568: 动态规划的0 - 1背包问题,请高手解释下代码 - ?
包沫复方: 这是清华算法设计C++描述上的代码吧?呵呵 我正巧读过. 简单解释一下吧 在解释之前你要知道动态规划是一个自底向上的过程 这个算法用到了一个二维数组m[][] 来存储各个坐标的价值信息 所以横坐标表示背包号码 纵坐标表示背包容量从1到...
湛河区15576592568: 求动态规划0 - 1背包算法解释 - ?
包沫复方: 01背包问题 题目 有N件物品和一个容量为V的背包.第i件物品的费用是c[i],价值是w[i].求解将哪些物品装入背包可使价值总和最大.基本思路 这是最基础的背包问题,特点是:每种物品仅有一件,可以选择放或不放.用子问题定义状态:即...
湛河区15576592568: 动态规划中的0 - 1背包问题怎么去理解?要求给出具体实例和详细步骤...?
包沫复方: * 一个旅行者有一个最多能用M公斤的背包,现在有N件物品, 它们的重量分别是W1,W2,...,Wn, 它们的价值分别为P1,P2,...,Pn. 若每种物品只有一件求旅行者能获得最大总价值. 输入格式: M,N W1,P1 W2,P2 ...... 输出格式: X */ 因为背包最大...
湛河区15576592568: 0 - 1背包问题具有贪心选择性质吗?证明之 - ?
包沫复方: 0-1背包问题不能用贪心法解决,但是部分背包问题可以用贪心法解决.首先0-1背包是要么不拿,要拿就得把这类物品全部拿完部分背包问题的贪心算法正确性证明可以参考这个看看
湛河区15576592568: C++能否解决0 - 1规划问题的递归解法 - ?
包沫复方: 背包问题有0-1背包问题和fraction背包问题,前者规定每个物品要么选,要么不选,而fraction knanpsack允许选取一个物品的一部分,0-1背包问题是NP难的,而fraction knapsacks的复杂度是O(n*logn), 只需要将单位物品的价值按降序排列,...
湛河区15576592568: 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[...
湛河区15576592568: 0 - 1背包问题用什么实现算法最好 - ?
包沫复方: 我们书上给的0-1背包问题是是用动态规划方法做的这个算法是动态规划的典型应用所以你把动态规划的思想搞清楚就应该可以理解了下面我把动态规划的思想给你说一下,希望对你有所帮助.哦..不好意思..时间不多了..你自己到网上找一下这方面的思想..然后结合一个实例认真研读一下..弄懂之后..你对动态规划..0-1背包问题就会有比较深入的理解.建议好好学一下算法..这对计算机专业学生来说很重要..我越来越觉得祝学有所成
湛河区15576592568: 动态规划之背包问题 - ?
包沫复方: P01:01背包问题 题目:有N件物品和一个容量为V的背包.第i件物品的费用是c[i],价值是w[i].求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量,且价值总和最大. 基本思路:这是最基础的背包问题,特点是:每种物品仅有一...