1. 求动态规划01背包问题c语言的代码,要稍微简单且无错的。谢谢
int c[10][100];/*对应每种情况的最大价值*/
int knapsack(int m,int n){ // 一个载重为m的背包 总共n个物品
int i,j,w[10],p[10];
printf("each weight & value :\n");
for(i=1;i<=n;i++)
scanf("%d %d",&w[i],&p[i]); // 第i个 物品的重量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;i++) //遍历每一个物品i
for(j=1;j<=m;j++) //假设背包的载重j为1、2、3、4、5、... ... m的情况
{
if(j >= w[i]) /*如果当前物品的重量 < 背包载重*/
{
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];
// c[i][j] = (p[i]+c[i-1][j-w[i]]>c[i-1][j])?(p[i]+c[i-1][j-w[i]]):(c[i-1][j]);
}
else c[i][j]=c[i-1][j];
}
return c[n][m];
}
int main()
{
int m,n;
printf("背包的承重量,物品的总个数:\n");
while(scanf("%d %d",&m,&n) != EOF){
printf("能装的最大总价值为%d",knapsack(m,n));
printf("\n");
}
return 0;
}
2. 关于这个java语言描述的0-1背包问题是否有错误?
有点问题:
public static void knapsack(int[]v,int[]w,int c,int[][]m)
{
int n=v.length-1;
int jMax=Math.min(w[n]-1,c);
for(int j=0;j<=jMax;j++)
m[n][j]=0;
for(int j=w[n];j<=c;j++)
m[n][j]=v[n];
for(int i=n-1;i>1;i--)
{
jMax=Math.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]=Math.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]=Math.max(m[1][c],m[2][c-w[1]]+v[1]);
}
public static void traceback(int[][]m,int[]w,int c,int[]x)
{
int n=w.length-1;
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]>0)?1:0;
}
//int n=w.length-1;
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]>0)?1:0;
}
3. 用动态规划算法怎样求解01背包问题
动态规划主要解决的是多阶段的决策问题。
01背包中,状态为背包剩余的容量,阶段是每一个物品,决策是是否选择当前的物品。
所以用动态规划来解决是非常贴切的。
我们设f[V]表示已经使用容量为V时所能获得的最大价值,w[i]表示i物品的质量,c[i]表示i物品的价值。
for(int i=1;i=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背包问题
4. 动态规划 01背包c++
#include
#include
int c[50][50];
int w[10],v[10];
int x[10];
int n;
void KNAPSACK_DP(int n,int W);
void OUTPUT_SACK(int c[50][50],int k) ;
void KNAPSACK_DP(int n,int W)
{
int i,k;
for(k=0;k<=W;k++)
c[0][k]=0;
for(i=1;i<=n;i++)
{
c[i][0]=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[50][50],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[1]=(c[1][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");
}
5. 动态规划算法实现求解0/1背包问题程序,输入应该放入背包中的物品的序号及背包中的总价值。 附:初始化
#include
int list[200][200];
int x[15];
int n;
int c;
int s;
int max (int a,int b)
{
if(a>b)return a;
else return b;
}
int ks(int n,int weight[],int value[],int x[],int c)
{
int i,j;
for(i=0;i<=n;i++)
list[i][0]=0;
for(j=0;j<=c;j++)
list[0][i]=0;
for(i=0;i<=n-1;i++)
for(j=0;j<=c;j++)
if(j<weight[i])
list[i][j]=list[i-1][j];
else
list[i][j]=max(list[i-1][j],list[i-1][j-weight[i]]+value[i]);
j=c;
for(i=n-1;i>=0;i--){
if(list[i][j]>list[i-1][j]){
x[i]=1;
j=j-weight[i];
}else x[i]=0;
}
printf("背包中的物品序列号:\n");
for(i=0;i<n;i++)
printf("%d\n",x[i]);
return list[n-1][c]; }
void main(){
int weight[15]={2,2,6,5,4};
int value[15]={6,3,5,4,6};
c=10;
n=5;
s=ks(n,weight,value,x,c);
printf("背包中的总价值:\n");
printf("%d\n",s);
}
6. 01背包 动态规划算法
嗯。。。错误上说了嘛,max的第二个参数错了,原参数:V[i-1][j-w[i]]+V[i],加数V[i]是int*类型的,当然不能和被加数相加啦
7. 用动态规划解决0-1背包问题时,它的最优子结构是什么
在前n个物品中 耗费体积V 取得的最大价值 dp[n][v]
8. C语言动态规划之背包问题求解
#include
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[i][0],&data[i][1]);
} //我是数组从第一个开始记得,看着容易理解,没必要去省那么几B的内存
for(i=0;i<=m;i++) f[0][i]=0;
for(i=0;i<=n;i++) f[i][0]=0;
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
{
f[i][j]=0;
if (j>=data[i][0])
{
f[i][j]=max(f[i-1][j],f[i-1][j-data[i][0]]+data[i][1]);
//对于这件物品要么不选要么选,不选是f[i-1][j];
//选的话为f[i-1][j-data[i][0]]此处j-data[i][0]是因为要选上一次就得少背j-data[i][0]的重量
//才能装下这次的物品
}
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就能够做出来了).
一句话:要多思考,反复思考
我很久没碰算法了,我没现成的代码这是我手打出来的,求分