| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 646 人关注过本帖
标题:[求助]0-1背包问题
只看楼主 加入收藏
summersun
Rank: 1
等 级:新手上路
帖 子:27
专家分:0
注 册:2005-12-29
收藏
 问题点数:0 回复次数:2 
[求助]0-1背包问题

如今的教科书都是很多打印错误的,下面的程序是我根据书上的程序修改过的,但是不能得出正确结果,请教一下各位大虾,是什么问题呢,知道的解析一下,先谢了。

#include<iostream>
using namespace std;

template <class Type>
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(int j=w[n];j<=c;j++)
m[n][j]=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]);
}
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 <class Type>
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;
}
}

void main()
{
int W[5]={2,2,6,5,4},V[5]={6,3,5,4,6};
int n=5,c=10;
int **M;
M=new int *[5];
for(int j=0;j<11;j++)
M[j]=new int;
Knapsack(V,W,10,n-1,M);
int X[6];
Traceback(M,W,10,n,X);
cout<<"得出0-1向量:";
for(int h=0;h<5;h++)
cout<<X[h]<<" ";
}

[此贴子已经被作者于2006-11-3 14:03:47编辑过]

搜索更多相关主题的帖子: 背包 
2006-11-02 18:00
dlcdavid
Rank: 3Rank: 3
来 自:成都
等 级:新手上路
威 望:6
帖 子:193
专家分:0
注 册:2005-12-23
收藏
得分:0 
什么东西

为了C++,我放弃了课本
为了高考,我又放弃了C++
现在而今眼目下,我能做什么?www.
2006-11-02 19:14
leowsw
Rank: 1
等 级:新手上路
帖 子:17
专家分:0
注 册:2006-11-4
收藏
得分:0 

min和max未定义,可以用a<b?a:b代替,改后还有解法上的错误
#include<iostream>
#include<cmath>
using namespace std;

template <class Type>
void Knapsack(Type *v,int *w,int c,int n,Type **m)
{
int jMax=(w[n]-1)>c?c:w[n]-1;
for(int j=0;j<=jMax;j++)
m[n][j]=0;
for(j=w[n];j<=c;j++)
m[n][j]=v[n];

for(int i=n-1;i>1;i--)
{
jMax=(w[i]-1)>c?c:w[i]-1;
for(j=0;j<=jMax;j++)
{
m[i][j]=m[i+1][j];
}
for(j=w[i];j<=c;j++)
m[i][j]=m[i+1][j]>m[i+1][j-w[i]]+v[i]?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]=m[1][c]>m[2][c-w[1]]+v[1]?m[1][c]:m[2][c-w[1]]+v[1];
}

template <class Type>
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;
}
}

void main()
{
int W[5]={2,2,6,5,4},V[5]={6,3,5,4,6};
int n=5,c=10;
int **M;
M=new int *[5];
for(int j=0;j<11;j++)
M[j]=new int;
Knapsack(V,W,10,n-1,M);
int X[6];
Traceback(M,W,10,n,X);
cout<<"得出0-1向量:";
for(int h=0;h<5;h++)
cout<<X[h]<<" ";
}

2006-11-05 13:39
快速回复:[求助]0-1背包问题
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.030771 second(s), 7 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved