编程论坛 → C++教室

背包问题

lindayanglong 发布于 2008-09-26 16:33， 1053 次点击

要解决的问题是这样的：假设箱子的容积是5，物体有4个，其体积分别为1，2，3，4问有多少种方法填充。那么结果应该是1，4  和2，3。下面的程序是书上的，但还是不对，请大家帮忙看看
#include<iostream>
using namespace std;
int *pout;
int mval;
int nval;
void calfun(int m,int n)
{
    if((m!=1&&n==1)||(m<1)||(n<1))
        return;
    if(m==n)

    {
        pout[n]=1;
        for(int i=1;i<=n;++i)
        {
            if(pout[i])
            cout<<i<<" ";
        }
            cout<<endl;
            pout[n]=0;
    }
    calfun(m-n,n-1);
    pout[n]=0;

    calfun(m,n-1);
    pout[n]=1;


}
void main()
{
    cin>>mval;
    cin>>nval;
    if(mval<nval)
        mval=nval;
    pout=new int [nval+1];
    memset(pout,0,(nval+1)*sizeof(int));
    calfun(mval,nval);
    delete [] pout;
}

5 回复

#2

sunkaidong2008-09-26 16:58

#include "stdafx.h"
#include<iostream>
using namespace std;
int a[4]={1,2,3,4};
int calfun(int m,int n)
{
    if((m<0))
        return 0;
    if(m==0)
        return 1;
    if(m-a[n]>=0&&calfun(m-a[n],n-1))
    {
        cout<<a[n];
        return 1;
    };
    calfun(m,n-1);
};
void main()
{
    int m;
    int n;
    cin>>m;
    cin>>n;//这里n=3最好
    calfun(m,n);
}

#3

sunkaidong2008-09-26 17:04

#include "stdafx.h"
#include<iostream>
using namespace std;
int a[9]={1,2,3,4,5,6,7,8,9};
int calfun(int m,int n)
{
    if((m<0))
        return 0;
    if(m==0)
    {
        cout<<"找到一个背包组合：";
        return 1;
    }
    if(m-a[n]>=0&&calfun(m-a[n],n-1))
    {
        cout<<a[n]<<' ';
        return 1;
    };
    calfun(m,n-1);
};
void main()
{
    int m;
    int n;
    cin>>m;
    cin>>n;
    calfun(m,n);
}

#4

中学者2008-09-27 09:37

LS是dfs...

#5

liyanhong2008-09-27 09:59

路过哈……

#6

lindayanglong2008-09-27 11:37

LS是dfs...
什么意思请讲

1