|
/*
Name: 背包问题
Date: 29-11-07 20:30
Description: 采用的方法为动态规划,参考<算法设计技巧与分析>
该方法只能输出一个结果,并且有些细节有待改进.
测试:
***************knapstack.txt**************
4 9
ab
2 3
cd
3 4
ef
4 5
gh
5 7
******************************************
结果:
*************knapstack_re.txt*************
ab
2 3
cd
3 4
ef
4 5
*****************************************
*/
#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
#define MAX 60
const char* INPUT_FILE = "knapstack.txt";
const char* OUTPUT_FILE = "knapstack_re.txt";
char name[MAX][MAX]; //存储物品名
int s[MAX]; //存储物品体积
int v[MAX]; //存储物品价值
int u[MAX][MAX]; //一个用来模仿递归的矩阵.
int b[MAX][MAX]; //1:选择了u[i-1] 2:没选择u[i-1]
FILE *in,*out;
void knapstack(int n,int sum);
void print_knapstack();
//背包算法.
void knapstack(int n,int sum)
{
int i,j;
for(i = 0;i <= n;i ++)
u[i][0] = 0;
for(j = 0; j <= sum ; j ++)
u[0][j] = 0;
for(i = 1; i <= n; i ++)
for(j = 1;j <= sum ;j ++)
{
u[i][j] = u[i-1][j];
b[i][j] = 1;
if(s[i-1] <= j && u[i-1][j-s[i-1]] + v[i-1] > u[i][j])
{
u[i][j] = u[i-1][j-s[i-1]] + v[i-1];
b[i][j] = 2;
}
}
/*调试用
for(i = 0;i <=n;i++)
{
for(j = 0;j <=sum;j ++)
printf("%d ",u[i][j]);
printf("\n");
}
for(i = 0;i <=n;i++)
{
for(j = 0;j <=sum;j ++)
printf("%d ",b[i][j]);
printf("\n");
}
*/
}
//打印结果
void print_knapstack(int n,int sum)
{
if(n == 0 || sum < 0)
return;
if(b[n][sum] == 2)
{
print_knapstack(n-1,sum - s[n-1]);
// printf("%d %d\n",n,sum-s[n-1]);
fputs(name[n-1],out);
fprintf(out,"%d %d\n",s[n-1],v[n-1]);
}
else
{
print_knapstack(n-1,sum);
// printf("%d %d\n",n,sum);
}
}
int main()
{
int i,j,num,sum;
if((in = fopen(INPUT_FILE,"r")) == NULL || (out = fopen(OUTPUT_FILE,"w")) == NULL)
{
printf("Can't open the file.");
getch();
return 1;
}
fscanf(in,"%d %d ",&num,&sum); //num:物品数量 sum:总共能装下的体积
for(i = 0;i < num ;i ++)
{
fgets(name[i],MAX,in);
fscanf(in,"%d %d ",&s[i],&v[i]); //s[i]:第i个物品的体积,v[i]: 第i个物品的价值
}
/*调试
for(i =0;i {
printf("%s%d %d\n",name[i],s[i],v[i]);
}
*/
knapstack(num,sum);
print_knapstack(num,sum);
fclose(in);
fclose(out);
return 0;
}
|
