物品编号 占据空间 价值 （1 2 1）（2 3 4）（3 4 3）（4 5 6）（5 6 8）。我现在编了一个程序，但是没有按照我想的得出结果。我的思路是这样的：用一个数组代表已经取得的物品。一个一个物品往里面装，然后判断（我设了一个价格a，全局变量），如果数组里物品的空间小于12（背包的空间就是12），在判断价值与a相比，如果比a大，将价值赋给a，打印。如果不是，将别的物品装入数组。我的源程序如下。求大虾帮忙找出问题在哪里呀。。。。一定要在我的程序上找出问题呀！因为我还编了另外的程序，所以我知道那个程序的结果不对，求大虾帮忙找出错误啦！
其实大家可以把我的程序运行一下就知道错误啦！就是说物品1占2个空间价值为1，等等，现在往背包（空间为12）里装东西。求最大的价值。我把每个子程序都解释一下吧。chushihua(struct bianhao q[5])初始化，给结构体赋值，就是规则给一下
jisuanquld(int s[5])计算数组装入物品的多少，就是一共装了多少东西
int jisuanprice(int s[5],int n)//计算数组装入物品的价值
int jisuanspace(int s[5],int n)//计算数组装入物品的空间
void print(int s[5],int n)打印数组里的东西，数组里面表示物品的编号
int zhuangru(int s[],int n,int a)//s表示已经装入,n表示现在从编号为n的开始取，a表示价值,最开始n为0，这里开始就是用回溯法做的呀！求大神帮忙呀！
#include <stdio.h>
struct bianhao
{
    int space;
    int price;
}q[5];
static int sumspace=0,sumprice=0,p=1;
int a=0;
void chushihua(struct bianhao q[5])
{
    q[0].price=1;q[0].space=2;
    q[1].price=4;q[1].space=3;
    q[2].price=3;q[2].space=4;
    q[3].price=6;q[3].space=5;
    q[4].price=8;q[4].space=6;
}
int jisuanquld(int s[5])
{
    int a,i;
    a=0;
    for(i=0;i<5;i++)
    {
        if(s[i]!=-1)
            a++;
    }
    return a;
}
int jisuanprice(int s[5],int n)
{
    int a,i;
    a=0;
    for(i=0;i<n;i++)
    {
        a+=q[s[i]].price;
    }
    return a;
}
int jisuanspace(int s[5],int n)
{
    int a,i ;
    a=0;
    for(i=0;i<n;i++)
    {
        a+=q[s[i]].space;
    }
    return a;
}
void print(int s[5],int n)
{
    printf("----------------------------\n");
    printf("    第%d种方法\n",p++);
    int i,x,y;
    y=jisuanprice(s,n);
    x=jisuanspace(s,n);
    for(i=0;i<n;i++)
    {
        if(s[i]!=-1)
        {            
            printf("      %d     %d     %d    \n",s[i]+1,q[s[i]].space,q[s[i]].price);
        }
    }

    printf("占据总空间为：%d    总价值为：%d\n",x,y);
}

int   zhuangru(int s[],int n,int a)//s表示已经装入,n表示现在从编号为n的开始取，a表示价值,最开始n为0
{
    int sumprice,sumspace,i,b,z;
    b=jisuanquld(s);
    sumprice=jisuanprice(s,b);
    sumspace=jisuanspace(s,b);
    if(sumspace==12)
    {
        if(sumprice>a)
        {
            a=sumprice;
            print(s,b);
            return 0;
        }
    }
    else if(sumspace>12)
    {
        sumprice=jisuanprice(s,b-1);
        z=sumspace-q[s[b-1]].space;
        if(z>12)  return 0;
        if(sumprice>a)
        {
            a=sumprice;
            print(s,b-1);
            return 0;
        }
    }
    for(i=n;i<5;i++)
    {
        s[b]=i;
        zhuangru(s,i+1,a);
    }
}
void main()
{
    int s[5]={-1,-1,-1,-1,-1};
    printf("商品编号  大小    价值\n");
    chushihua(q);
    int n;
    n=0;
    zhuangru(s,n,a);
    printf("\n");
}
实际上，正确答案是第四和第五物品的东西，价值是14的，但是，这个程序运行后，答案不对。

01背包问题？

/* 01背包 f[i][j]=max(f[i-1][j], f[i-1][j-v[i]] +p[i]) */
#include <stdio.h>
#include <stdlib.h>
#define MAX(A,B) ((A)>(B)?(A):(B))
#define SIZE   5
#define MAXVOL 12

int main(void)
{
    int v[SIZE] = {2,3,4,5,6};  // 体积
    int p[SIZE] = {1,4,3,6,8};  // 价值
    int kp[MAXVOL + 1] = {0};   // 背包
    int i,j,max=0;

    for (i=0; i<SIZE; ++i) {
        for (j=MAXVOL; j>=v[i]; --j) {
            kp[j]=MAX(kp[j], kp[j-v[i]] +p[i]);
            max=MAX(kp[j], max);
        }
    }
    
    printf("MAX VALUE: %d\n", max);
    system("Pause");
    return 0;
}

[ 本帖最后由 cosdos 于 2011-11-25 11:17 编辑 ]

你的程序难以阅读

动态规划  或者 搜索

三楼的能把能把你的思路给你说一下，我看了很久没有看懂呀。。。。。。。