背包装东西的问题

物品编号 占据空间  价值  （1 2 1）（2 3 4）（3 4 3）（4 5 6）（5 6 8）。我现在编了一个程序，但是没有按照我想的得出结果。我的思路是这样的：用一个数组代表已经取得的物品。一个一个物品往里面装，然后判断（我设了一个价格a，全局变量），如果数组里物品的空间小于12（背包的空间就是12），在判断价值与a相比，如果比a大，将价值赋给a，打印。如果不是，将别的物品装入数组。我的源程序如下。求大虾帮忙找出问题在哪里呀。。。。一定要在我的程序上找出问题呀！因为我还编了另外的程序，所以我知道那个程序的结果不对，求大虾帮忙找出错误啦！

#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");
}

5 个解决方案

#1

背包问题是典型的DP，详见DP，
不要动不动就要别人帮你找代码里面的错误，自己好好整理下思路，再按图索骥
浪费别人时间。

#2

看了几遍，表示还是看不懂

#3

楼主弄个英语词典吧

#4

其实大家可以把我的程序运行一下就知道错误啦！就是说物品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，这里开始就是用回溯法做的呀！求大神帮忙呀！

#5

#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;
}