Question

01背包问题 麻烦帮忙改错

格式：
第一行：总体积 总物品数n
接下来的n行为：
所占空间 价值
输出：
一个数据（表示所能获得的最大价值）
举例：
INPUT：
100 5
77 92
22 22
29 87
50 46
99 90

OUTPUT：
133
====================================
以下是我的程序 ：
输出的答案有错误，例子就过不去
#include<stdio.h>
#include<stdlib.h>
#define MAX_GOLD 100
#define MAX_PEOPLE 1000
int n,
people_total,
gold[MAX_GOLD]={0},
peopleneed[MAX_GOLD]={0},
array_re[MAX_GOLD][MAX_PEOPLE+1];
///////////////////////////////////
void pre();
int work(int b,int people);
void ffread();
void ffwrite(int ans);
///////////////////////////////////
int main()
{
ffread();
pre();
ffwrite(work(0,people_total));
return 0;
}
void pre()
{
for(int i=0;i<MAX_GOLD;i++)
for(int j=0;j<=MAX_PEOPLE;j++)
array_re[i][j]=-1;
}
int work(int b,int people) //b=the number of rest goldkuang ;people=people rest
{
if(array_re[b][people]!=-1);
else if(b==n-1)
{
if(people>=peopleneed[b])
array_re[b][people]=gold[b];
else
array_re[b][people]=0;
}
else
{
int t0,t1;
t0=work(b+1,people);
if(peopleneed[b]<=people)
{
t1=work(b+1,people-peopleneed[b]);
if(t0>t1)
array_re[b][people]=t0;
else
array_re[b][people]=t1+gold[b];
}
else
array_re[b][people]=t0;
}
return array_re[b][people];
}
void ffread()
{
FILE *fp;
fp=fopen("gold.in","r");
fscanf(fp,"%d %d",&people_total,&n);
for(int i=0;i<n;i++)
fscanf(fp,"%d %d",&peopleneed[i],&gold[i]);
fclose(fp);
}
void ffwrite(int ans)
{
FILE *fp;
fp=fopen("gold.out","w");
fprintf(fp,"%d",ans);
fclose(fp);
printf("%d",ans);
system("pause");
}

Answer 1

不好意思。我刚看到你发的信息。
这道题是个dp问题。可以写出它的动态规划转移方程f[i][j]=max{ f[i-1][j] , f[i-1][j-w[i]] + c[i] },最后的答案是f[n][V]。你可以试着编一个简单的数据模拟一下，以增强对这道题的理解。
另外，你可以按照这个转移方程来写，也可以按照我的程序来写。我的程序跟这个方程的思路是一样的，但降低了空间复杂度。
还有 for(j=V; j>=w[i]; --j)，这句如果按递增的顺序写的话，就成了完全背包问题。不过如果开的是二维数组，就还是01背包。
如果你想了解更多，你可以在百度文库里搜一下背包九讲，那里面讲得很详细。

我打了一个。我用C++写的，C的文件读取太麻烦了，希望你能看懂
#include<fstream>

using namespace std;

ifstream cin("gold.in");
ofstream cout("gold.out");

int V,n;
int w[10001]={0},c[10001]={0};
int f[10001]={0};

void work()
{
int i,j;
for(i=1; i<=n; ++i)
for(j=V; j>=w[i]; --j)
if(f[j]<f[j-w[i]]+c[i]) f[j]=f[j-w[i]]+c[i];
}

int main()
{
cin>>V>>n;
for(int i=1; i<=n; ++i)
cin>>w[i]>>c[i];

work();

cout<<f[V];

return 0;
}