本文目录
- dp动态规划中的背包问题01
- 求动态规划0-1背包算法解释
- c语言01背包问题动态规划出错麻烦各位帮忙纠错一下，谢谢
- C语言动态规划之背包问题求解
- 动态规划 01背包c++
- 01背包问题
- c语言01背包问题谁能简单说下
- 用动态规划算法怎样求解01背包问题
- 关于C++ 01背包问题
- 用动态规划算法和贪婪算法求解01背包问题的区别
dp动态规划中的背包问题01
（1）
将二维数组转化为一维数组之后，f[v]表示v的容量最多装多大价值。
如果顺序枚举的话，每种物品可能多次使用。例如某个物品重量为5，价值为10，那么就会用f去更新f，用f去更新f，最后出现f=0，f=10，f=20的情况。而这是01背包，要求每种物品只能用一次。
逆序枚举时，是在f被f更新之前，就用f更新f，这样就可以保证用一次。
（2）
首先要搞明白f[i][v]的定义：用前i种物品恰好装满一个容量为v的背包，最大价值是多少。
这句话的意思就是说，费用总和为v的状态可能没有意义。譬如说所有物品加在一起的重量都不到v，那么f[N][V]必然没有意义了。只能去找f[N][0..V]中的最大值来输出。
但是如果我们改变一下f[i][v]的定义：用前i种物品，在总重不超过v的情况下，最大价值是多少。
就可以直接输出f[N][V]了，这样只需要改变一下转移方程，加上一项f[i][v-1]。
还有问题请追问。
求动态规划0-1背包算法解释
01背包问题
题目
有N件物品和一个容量为V的背包。第i件物品的费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使价值总和最大。
基本思路
这是最基础的背包问题，特点是：每种物品仅有一件，可以选择放或不放。
用子问题定义状态：即f[i][v]表示前i件物品恰放入一个容量为v的背包可以获得的最大价值。则其状态转移方程便是：
f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]}
这个方程非常重要，基本上所有跟背包相关的问题的方程都是由它衍生出来的。所以有必要将它详细解释一下：“将前i件物品放入容量为v的背包中”这个子问题，若只考虑第i件物品的策略（放或不放），那么就可以转化为一个只牵扯前i-1件物品的问题。如果不放第i件物品，那么问题就转化为“前i-1件物 品放入容量为v的背包中”，价值为f[i-1][v]；如果放第i件物品，那么问题就转化为“前i-1件物品放入剩下的容量为v-c[i]的背包中”，此时能获得的最大价值就是f[i-1][v-c[i]]再加上通过放入第i件物品获得的价值w[i]。
优化空间复杂度
以上方法的时间和空间复杂度均为O(VN)，其中时间复杂度应该已经不能再优化了，但空间复杂度却可以优化到O。
先考虑上面讲的基本思路如何实现，肯定是有一个主循环i=1..N，每次算出来二维数组f[i][0..V]的所有值。那么，如果只用一个数组 f[0..V]，能不能保证第i次循环结束后f[v]中表示的就是我们定义的状态f[i][v]呢？f[i][v]是由f[i-1][v]和f[i-1] [v-c[i]]两个子问题递推而来，能否保证在推f[i][v]时（也即在第i次主循环中推f[v]时）能够得到f[i-1][v]和f[i-1] [v-c[i]]的值呢？事实上，这要求在每次主循环中我们以v=V..0的顺序推f[v]，这样才能保证推f[v]时f[v-c[i]]保存的是状态 f[i-1][v-c[i]]的值。伪代码如下：
for i=1..N
for v=V..0
f[v]=max{f[v],f[v-c[i]]+w[i]};
其中的f[v]=max{f[v],f[v-c[i]]}一句恰就相当于我们的转移方程f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]}，因为现在的f[v-c[i]]就相当于原来的f[i-1][v-c[i]]。如果将v的循环顺序从上面的逆序改成顺序的话，那么则成了f[i][v]由f[i][v-c[i]]推知，与本题意不符，但它却是另一个重要的背包问题P02最简捷的解决方案，故学习只用一维数组解01背包问题是十分必要的。
事实上，使用一维数组解01背包的程序在后面会被多次用到，所以这里抽象出一个处理一件01背包中的物品过程，以后的代码中直接调用不加说明。
过程ZeroOnePack，表示处理一件01背包中的物品，两个参数cost、weight分别表明这件物品的费用和价值。
procedure ZeroOnePack(cost,weight)
for v=V..cost
f[v]=max{f[v],f[v-cost]+weight}
注意这个过程里的处理与前面给出的伪代码有所不同。前面的示例程序写成v=V..0是为了在程序中体现每个状态都按照方程求解了，避免不必要的思维复杂度。而这里既然已经抽象成看作黑箱的过程了，就可以加入优化。费用为cost的物品不会影响状态f[0..cost-1]，这是显然的。
有了这个过程以后，01背包问题的伪代码就可以这样写：
for i=1..N
ZeroOnePack(c[i],w[i]);
初始化的细节问题
我们看到的求最优解的背包问题题目中，事实上有两种不太相同的问法。有的题目要求“恰好装满背包”时的最优解，有的题目则并没有要求必须把背包装满。一种区别这两种问法的实现方法是在初始化的时候有所不同。
如果是第一种问法，要求恰好装满背包，那么在初始化时除了f为0其它f[1..V]均设为-∞，这样就可以保证最终得到的f[N]是一种恰好装满背包的最优解。
如果并没有要求必须把背包装满，而是只希望价格尽量大，初始化时应该将f[0..V]全部设为0。
为什么呢？可以这样理解：初始化的f数组事实上就是在没有任何物品可以放入背包时的合法状态。如果要求背包恰好装满，那么此时只有容量为0的背包可能被价值为0的nothing“恰好装满”，其它容量的背包均没有合法的解，属于未定义的状态，它们的值就都应该是-∞了。如果背包并非必须被装满，那么 任何容量的背包都有一个合法解“什么都不装”，这个解的价值为0，所以初始时状态的值也就全部为0了。
这个小技巧完全可以推广到其它类型的背包问题，后面也就不再对进行状态转移之前的初始化进行讲解。
一个常数优化
前面的伪代码中有 for v=V..1，可以将这个循环的下限进行改进。
由于只需要最后f[v]的值，倒推前一个物品，其实只要知道f[v-w[n]]即可。以此类推，对以第j个背包，其实只需要知道到f[v-sum{w[j..n]}]即可，即代码中的
for i=1..N
for v=V..0
可以改成
for i=1..n
bound=max{V-sum{w[i..n]},c[i]}
for v=V..bound
这对于V比较大时是有用的。
小结
01背包问题是最基本的背包问题，它包含了背包问题中设计状态、方程的最基本思想，另外，别的类型的背包问题往往也可以转换成01背包问题求解。故一定要仔细体会上面基本思路的得出方法，状态转移方程的意义，以及最后怎样优化的空间复杂度。
c语言01背包问题动态规划出错麻烦各位帮忙纠错一下，谢谢
你这是完全背包。01背包每个物品只能装一次，因此必须和上一个物品比较，否则会出现重复装的情况。
f[i][j]表示把前i个物品装入容量为j的箱子能得到的最大价值
则有：
f[i][j]=max(f[i-1][j]/*不装*/,f[i-1][j-c]+v/*装，但必须满足j》=c*/)
改好的代码如下所示：
#include 《algorithm》
#include 《iostream》
#include 《string.h》
using namespace std;
int main(int argc, char *argv)
{
int c = {0,5,3,4,3,5};//消耗
int v = {0,500,200,300,350,400}; // value
int f;
memset(f,0,sizeof(f)); //归位0
for(int i = 1; i 《= (sizeof(c)/sizeof(int) - 1); i++) //i 第几个物品
{
for(int p = 1; p 《= 10; p++) //表示10 个空间
{
if(p 《 c[i])
{
f[i][p] = f[i][p - 1];
}
else
{
// f[i][p] = max(f[i - 1][p], f[i][p - c[i]] + v[i]);
f[i][p] = max(f[i - 1][p], f[i - 1][p - c[i]] + v[i]);
}
}
}
printf(“%d“,f);
return 0;
}
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;
int f;
scanf(“%d%d“,&n,&m); //n表示个数，m表示能背的最大重量
for(i=1;i《=n;i++)
{
scanf(“%d%d“,&data[i],&data[i]);
} //我是数组从第一个开始记得，看着容易理解，没必要去省那么几B的内存
for(i=0;i《=m;i++) f[i]=0;
for(i=0;i《=n;i++) f[i]=0;
for(i=1;i《=n;i++)
for(j=1;j《=m;j++)
{
f[i][j]=0;
if (j》=data[i])
{
f[i][j]=max(f[i-1][j],f[i-1][j-data[i]]+data[i]);
//对于这件物品要么不选要么选，不选是f[i-1][j];
//选的话为f[i-1][j-data[i]]此处j-data[i]是因为要选上一次就得少背j-data[i]的重量
//才能装下这次的物品
}
else f[i][j]=f[i-1][j];
}
printf(“%d\n“,f[n][m]);
return 0;
}
然后常见的背包问题还有多重背包问题，对于每一个物品可能有多个这种可以预处理成一般的背包问题，就是把几个摊开，很简单就不解释了，当然也可以加一维.
还有就是完全背包问题他的状态转移方程是f[i,j]=max(f[i-1][j],f[i][j-data[i].v]);
他和01的区别只是要选的时候不是f[i-1][j-data[i].v]而是f[i][j-data[i].v]，这样就能选到自己了，如果是初学可能不好理解，慢慢理会吧，其实这个很妙，我当初用了很多种方法，都是错的，看了一时也没明白，后来豁然开朗，然后对动规的理解都上了一个层次.
还有就是多为背包，这个只需要加一维，理解了前面的自然就能做出来了，根本不需要再看状态转移方程了（事实上理解后01就能够做出来了）.
一句话：要多思考，反复思考
我很久没碰算法了，我没现成的代码这是我手打出来的，求分
动态规划 01背包c++
#include《stdio.h》
#include《stdlib.h》
int c;
int w,v;
int x;
int n;
void KNAPSACK_DP(int n,int W);
void OUTPUT_SACK(int c,int k) ;
void KNAPSACK_DP(int n,int W)
{
int i,k;
for(k=0;k《=W;k++)
c[k]=0;
for(i=1;i《=n;i++)
{
c[i]=0;
for(k=1;k《=W;k++)
{
if(w[i]《=k)
{
if(v[i]+c[i-1][k-w[i]]》c[i-1][k])
c[i][k]=v[i]+c[i-1][k-w[i]];
else
c[i][k]=c[i-1][k];
}
else
c[i][k]=c[i-1][k];
}
}
}
void OUTPUT_SACK(int c,int k)
{
int i;
for(i=n;i》=2;i--)
{
if(c[i][k]==c[i-1][k])
x[i]=0;
else
{
x[i]=1;
k=k-w[i];
}
}
x=(c[k]?1:0);
for(i=1;i《=n;i++)
printf(“%4d“,x[i]);
}
void main()
{
int m;
int i,j,k;
printf(“输入物品个数:“);
scanf(“%d“,&n);
printf(“依次输入物品的重量:\n“);
for(i=1;i《=n;i++)
scanf(“%d“,&w[i]);
printf(“依次输入物品的价值:\n“);
for(i=1;i《=n;i++)
scanf(“%d“,&v[i]);
printf(“输入背包最大容量:\n“);
scanf(“%d“,&m);
for(i=1;i《=m;i++)
printf(“%4d“,i);
printf(“\n“);
KNAPSACK_DP(n,m);
printf(“构造最优解过程如下:\n“);
for(j=1;j《=5;j++)
{
for(k=1;k《=m;k++)
printf(“%4d“,c[j][k]);
printf(“\n“);
}
printf(“最优解为:\n“);
OUTPUT_SACK(c,m);
system(“pause“);
}
01背包问题
0/1背包
一个旅行者有一个最多能用m公斤的背包，现在有n件物品，它们的重量分别是W1，W2，...,Wn,它们的价值分别为C1,C2,...,Cn.若每种物品只有一件求旅行者能获得最大总价值。
《1》分析说明:
显然这个题可用深度优先方法对每件物品进行枚举(选或不选用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.
c语言01背包问题谁能简单说下
01背包问题就是有个容量为W的包，然后有一堆的物品(1...n)，其中wi、vi分别为第i个物品的重量和价值，现在需要求的就是使得包中所装的物品尽可能的价值高。那么这个物品放不放在包中对应取值0
or
1。其算法为动态规划，需要证明最优子结构性质。用s[i][j]表示只有前i个物品且包容量为j时所能等到的最大价值，而有递归式
s[i][j]=
s[i-1][j],
wi》j
max{s[i-1][j],s[i-1][j-wi]+vi},
wi《=j
s[j]=0
1《=j《=W
s[i]=0
1《=i《=n
所以不论用什么语言实现，就是计算上面的式子，最终求得s[n][W]，上面的式子很好用递推实现的，这个是自底向上的，就是两层for；你也可以用栈实现自顶向下的，这个是记录式的方法。
以上的W是只考虑整数的。
用动态规划算法怎样求解01背包问题
动态规划主要解决的是多阶段的决策问题。
01背包中，状态为背包剩余的容量，阶段是每一个物品，决策是是否选择当前的物品。
所以用动态规划来解决是非常贴切的。
我们设f[V]表示已经使用容量为V时所能获得的最大价值，w[i]表示i物品的质量，c[i]表示i物品的价值。
for(int i=1;i《=n;i++)
for(int j=V;j》=w[i];j--)
f[j]=max(f[j],f[j-w[i]]+c[i]);
这便是所谓的一个状态转移方程。
f[j]表示在已经使用容量为j时的最大价值，f[j-w[i]]表示在已经使用容量为j-w[i]时的最大价值。
f[j]可以由f[j-w[i]]这个状态转移到达，表示选取w[i]这个物品，并从而获得价值为c[i]。
而每次f[j]会在选与不选中决策选出最优的方案。
从每一个物品，也就是每一个阶段的局部最优推出最后的全局最优值。这样就解决了01背包问题
关于C++ 01背包问题
1. 摘要
以背包问题为例，介绍了贪心法与动态规划的关系以及两个方案在解决背包问题上的比较。贪心法什么时候能取到最优界并无一般理论，但对于普通背包问题我们有一个完美的结果——贪心法可取到最优解。介绍了其它一些对背包问题的研究或者拓展。
2. 介绍
贪心算法是我们在《算法设计技巧与分析》这门课中所学习到的几种重要的算法之一，顾名思义，贪心算法总是作出在当前看来最好的选择。也就是该算法并不从整体最优考虑，它所作出的选择只是在某种意义上的从局部的最优选择，寻找到解决问题的次优解的方法。虽然我们希望贪心算法得到的最终结果也是整体最优的，但是在某些情况下，该算法得到的只是问题的最优解的近似。
3. 算法思想:
贪心法的基本思路：
——从问题的某一个初始解出发逐步逼近给定的目标，以尽可能快的地求得更好的解。当达到某算法中的某一步不能再继续前进时，算法停止。
该算法存在问题：
1. 不能保证求得的最后解是最佳的；
2. 不能用来求最大或最小解问题；
3. 只能求满足某些约束条件的可行解的范围。
实现该算法的过程：
在约束 下最大。
(2) 动态规划解决方案：是解决0/1背包问题的最优解
(i) 若i=0或j=0, V[i,j] = 0
(ii) 若j《si, V[i,j] = V[i-1,j] (仅用最优的方法，选取前i-1项物品装入体积为j 的背包，因为第i项体积大于j,装不下这一项，所以背包里面的i-1项就达到最大值)
(iii) 若i》0和j》=si, Max{V[i-1,j],V[i-1,j-si]+vi} (第一种情况是包中的i-1项已经达到最大值，第二种情况是i-1项占j-si的体积再加上第i项的总的价值，取这两种情况的最大值。)
//sj和vj分别为第j项物品的体积和价值，C是总体积限制。
//V[i,j]表示从前i项{u1,u2,…,un}中取出来的装入体积为j的背包的物品的最大//价值。
（3）贪心算法解决背包问题有几种策略：
(i) 一种贪婪准则为：从剩余的物品中，选出可以装入背包的价值最大的物品，利用这种规则，价值最大的物品首先被装入（假设有足够容量），然后是下一个价值最大的物品，如此继续下去。这种策略不能保证得到最优解。例如，考虑n=2, w=[100,10,10], p =[20,15,15], c = 105。当利用价值贪婪准则时，获得的解为x= [ 1 , 0 , 0 ]，这种方案的总价值为2 0。而最优解为[ 0 , 1 , 1 ]，其总价值为3 0。
(ii) 另一种方案是重量贪婪准则是：从剩下的物品中选择可装入背包的重量最小的物品。虽然这种规则对于前面的例子能产生最优解，但在一般情况下则不一定能得到最优解。考虑n= 2 ,w=[10,20], p=[5,100], c= 2 5。当利用重量贪婪策略时，获得的解为x =[1,0], 比最优解[ 0 , 1 ]要差。
(iii) 还有一种贪婪准则，就是我们教材上提到的，认为，每一项计算yi=vi/si,即该项值和大小的比，再按比值的降序来排序，从第一项开始装背包，然后是第二项，依次类推，尽可能的多放，直到装满背包。
有的参考资料也称为价值密度pi/wi贪婪算法。这种策略也不能保证得到最优解。利用此策略试解n= 3 ,w=[20,15,15], p=[40,25,25], c=30 时的最优解。虽然按pi /wi 非递（增）减的次序装入物品不能保证得到最优解，但它是一个直觉上近似的解。
而且这是解决普通背包问题的最优解，因为在选择物品i装入背包时，可以选择物品i的一部分，而不一定要全部装入背包，1≤i≤n。
如图1，大体上说明了动态规划解决的0／1背包问题和贪心算法解决的问题之间的区别，
图1
（4）贪心算法解决背包问题的算法实现：
代码如下：
#include 《iostream.h》
struct goodinfo
{
float p; //物品效益
float w; //物品重量
float X; //物品该放的数量
int flag; //物品编号
};//物品信息结构体
void Insertionsort(goodinfo goods,int n)
{//插入排序，按pi/wi价值收益进行排序，一般教材上按冒泡排序
int j,i;
for(j=2;j《=n;j++)
{
goods=goods[j];
i=j-1;
while (goods.p》goods[i].p)
{
goods[i+1]=goods[i];
i--;
}
goods[i+1]=goods;
}
}//按物品效益，重量比值做升序排列
void bag(goodinfo goods,float M,int n)
{
float cu;
int i,j;
for(i=1;i《=n;i++)
goods[i].X=0;
cu=M; //背包剩余容量
for(i=1;i《n;i++)
{
if(goods[i].w》cu)//当该物品重量大与剩余容量跳出
break;
goods[i].X=1;
cu=cu-goods[i].w;//确定背包新的剩余容量
}
if(i《=n)
goods[i].X=cu/goods[i].w;//该物品所要放的量
/*按物品编号做降序排列*/
for(j=2;j《=n;j++)
{
goods=goods[j];
i=j-1;
while (goods.flag《goods[i].flag)
{
goods[i+1]=goods[i];
i--;
}
goods[i+1]=goods;
}
///////////////////////////////////////////
cout《《“最优解为:“《《endl;
for(i=1;i《=n;i++)
{
cout《《“第“《《i《《“件物品要放:“;
cout《《goods[i].X《《endl;
}
}
void main()
{
cout《《“|--------运用贪心法解背包问题---------|“《《endl;
int j,n; float M;
goodinfo *goods;//定义一个指针
while(j)
{
cout《《“请输入物品的总数量：“;
cin》》n;
goods=new struct goodinfo [n+1];//
cout《《“请输入背包的最大容量：“;
cin》》M;
cout《《endl;
int i;
for(i=1;i《=n;i++)
{ goods[i].flag=i;
cout《《“请输入第“《《i《《“件物品的重量:“;
cin》》goods[i].w;
cout《《“请输入第“《《i《《“件物品的效益:“;
cin》》goods[i].p;
goods[i].p=goods[i].p/goods[i].w;//得出物品的效益，重量比
cout《《endl;
}
Insertionsort(goods,n);
bag(goods,M,n);
cout《《“press 《1》 to run agian“《《endl;
cout《《“press 《0》 to exit“《《endl;
cin》》j;
}
}
用动态规划算法和贪婪算法求解01背包问题的区别
首先这两个算法是用来分别解决不同类型的背包问题的，不存在哪个更优的问题。 当一件背包物品可以分割的时候，使用贪心算法，按物品的单位体积的价值排序，从大到小取即可。 当一件背包物品不可分割的时候，（因为不可分割，所以就算按物品的单位体积的价值大的先取也不一定是最优解）此时使用贪心是不对的，应使用动态规划。
