| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 3438 人关注过本帖
标题:求0/1背包问题的非递归算法
只看楼主 加入收藏
limeng_HOHO
Rank: 2
来 自:上海
等 级:论坛游民
帖 子:49
专家分:50
注 册:2007-7-16
收藏
 问题点数:0 回复次数:6 
求0/1背包问题的非递归算法
设被包容量为m,有n件物品,质量为m1,m2,...mn,均为正整数,要从n件物品中挑选若干使得背包质量之和正好为m。
书上给了递归算法,我想知道非递归算法,谢谢各位了
搜索更多相关主题的帖子: 非递归 算法 背包 物品 质量 
2007-10-12 20:04
卧龙孔明
Rank: 9Rank: 9Rank: 9
等 级:贵宾
威 望:59
帖 子:3872
专家分:684
注 册:2006-10-13
收藏
得分:0 
可以用DP

My Blog: www.aiexp.info
虽然我的路是从这里开始的,但是这里不再是乐土.感谢曾经影响过,引导过,帮助过我的董凯,飞燕,leeco,starwing,Rockcarry,soft_wind等等等等.别了,BCCN.
2007-10-12 20:39
永夜的极光
Rank: 6Rank: 6
等 级:贵宾
威 望:27
帖 子:2721
专家分:1
注 册:2007-10-9
收藏
得分:0 

据说递归算法都可以转变成非递归的算法


从BFS(Breadth First Study)到DFS(Depth First Study)
2007-10-12 21:01
pinglideyu
Rank: 3Rank: 3
来 自:武汉工程大学
等 级:论坛游侠
威 望:1
帖 子:735
专家分:140
注 册:2007-1-7
收藏
得分:0 
数据结构这本书上有讲怎么样将递归算法都可以转变成非递归的算法

~~我的明天我知道~~
2007-10-12 21:03
leeco
Rank: 4
等 级:贵宾
威 望:10
帖 子:1029
专家分:177
注 册:2007-5-10
收藏
得分:0 


#define MAXC 60000
int _dp[2][MAXC+1];
struct{
int* operator [] (int i){
return _dp[i&1];
}
}dp;

int knapsack(int* w,int* v,int n,int c){
for(int r=0;r<=c;r++){
if(w[0]>r)dp[0][r]=0;
else dp[0][r]=v[0];
}
for(int k=1;k<n;k++){
dp[k][0]=0;
for(int r=1;r<=c;r++){
dp[k][r]=dp[k-1][r];
if(r>=w[k] && dp[k-1][r-w[k]]+v[k]> dp[k][r]){
dp[k][r]=dp[k-1][r-w[k]]+v[k];
}
}
}
return dp[n-1][c];
}

2007-10-12 21:09
limeng_HOHO
Rank: 2
来 自:上海
等 级:论坛游民
帖 子:49
专家分:50
注 册:2007-7-16
收藏
得分:0 
回复:(pinglideyu)数据结构这本书上有讲怎么样将递...

是有 我也看了 但是没看明白。。。。。


世界并不美丽 然而又因此而美丽
2007-10-12 22:31
zhangyuan2000
Rank: 1
等 级:新手上路
帖 子:1
专家分:0
注 册:2008-11-1
收藏
得分:0 
背包问题
#include<iostream>
using namespace std;
#include<stdlib.h>
#define max 100

void Init_fun(int num);
void DiGui_fun(float a[], int b[], float tatol, int i, float T, int num);

int main()
{
    int num;

    cout<<"请输入你要输入物体得个数:";
    cin>>num;

    Init_fun( num );

    return 0;
}

void Init_fun(int num)
{
    int counter, i=0;
    float a[max];
    int b[max];
    float T=0, tatol=0;

    cout<<"请输入元素";
    a[0]=0;
    for(counter=1; counter<=num; counter++)
        cin>>a[counter];

    for(counter=0; counter<=num; counter++)
        b[counter]=0;
    
    cout<<"输入总重量:";
    cin>>T;

    DiGui_fun(a, b, tatol, i, T, num+1);

}


void DiGui_fun(float a[], int b[], float tatol, int i, float T, int num)
{
    
    tatol=tatol + a[i];
    
    if(tatol==T){
        for(int j=1; j<=i; j++){
            if(b[j]==1)
                cout<<a[j]<<"\t";
        }
        cout<<"\n";
    }
    else{
        for(int n=i+1; n<=num; n++){
            b[n]=1;
            DiGui_fun(a, b, tatol, n,T, num );
            b[n]=0;
        }
    }
}
2008-11-01 22:00
快速回复:求0/1背包问题的非递归算法
数据加载中...
 
   



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

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