Question

C语言数据结构 背包问题

#include<stdio.h>
#include<stdlib.h>
int knap(int s, int n, int w[])
{
if ( s == 0 )
return 1;
else
if ( (s<0) || (s>0 && n<1) )
return(0);
else
if ( knap(s - w[n-1], n - 1, w)==1 )
{
printf("result: n=%d ,w[%d]=%d\n", n, n-1, w[n-1]);
return 1;
}
else
return ( knap(s, n - 1, w) );
}
int main()
{
int* w;
int s = 0, n = 0, result = 0, i = 0;
printf("please input s = ");/*输入s*/
scanf("%d", &s);
printf("please input n = ");/*输入n*/
scanf("%d", &n);
w = (int*)malloc(n*sizeof(int));
v = (int*)malloc(n*sizeof(int));
printf("please input the %d numbers(weight):\n", n);/*输入重量*/
for (i = 0; i < n; i++)
scanf("%d", w+i);
result = knap(s, n, w);
if (result == 0)
printf("no solution!\n");
return 0;
}

这是一个0-1背包问题的代码。我想在中间加一个价值变量。求背包内装满并且价值最高。要怎么改？

Answer 1

子程序是什么情况……
一个二维循环就可以了啊
n:物品个数
m:最大空间
a[i]:物品大小
b[i]:物品价值
f[i]:i空间内最大价值（f[m]为答案）
for i=1...n
for j=a[i]...m
f[j]=max(f[j],f[j-a[i]]+b[i]);
是在不行可以看看背包九讲 不过那个有点恶心……

Answer 2

- - 代码 都有错。。 求分。。 就帮你改

追问

你先改着。我去搞分。

Answer 3

给你提示 贪心法

追问

这。。。你为难我了。。。求代码。、、、