目录

• FMethodPackage.c
• 运行结果示例
  • 1.5个物品，负重15
  • 2.20个物品，负重200

【TDTX】

FMethodPackage.c

#include <stdio.h>
#include <math.h>
#include <stdlib.h>
int main()
{
    int n,fz;
    int i,j;
    printf("输入物品个数和背包负重（n fz）:"); 
    scanf("%d %d",&n,&fz);
    int a[n][2];//C99
    
    printf("输入重量和价值：\n"); 
    for(i = 0;i < n;i++)
    {
        scanf("%d %d",&a[i][0],&a[i][1]);
        //printf("%d %d\n",a[i][0],a[i][1]);
    }
    
    int size = (int)pow(2,n);
    int** ls = (int**)malloc(sizeof(int*)*size);//创建一个指针数组，每个元素可以指向一个int*类型 
	for(i = 0;i < size;i++)
	{
		ls[i] = (int*)malloc(sizeof(int)*n);//将每个元素指向分配的一维数组 
	}
    
    for(i = 0;i < size;i++)
    {
    	//生成集合的全部子集 
    	int t;
        for(t = i,j = n-1;j >= 0;j--)
        {
            if(t == 0)
            {
                ls[i][j] = 0;
                continue;
            }
            ls[i][j] = t % 2;
            t = t / 2;
        }
    }

//下面代码用于检查所有的组合，即重量组合的全部0/1标记子集 
//    for(i = 0;i < size;i++)
//    {
//        for(j = 0;j < n;j++)
//        {
//            printf("%d ",ls[i][j]);
//        }
//        puts("");
//    }

    int w = 0;
    int v = 0;
    int maxv = 0;
    int gw = 0;
    int flag = -1;
    for(i = 0;i < size;i++)
    {
        for(w = 0,v = 0,j = 0;j < n;j++)
        {
            if(w < fz)
            {
                if(ls[i][j] == 1)
                {
                     w = w + a[j][0];
                     v = v + a[j][1];
                }
            }
            else
            {
                break;
            }
        }
        if(maxv < v && w <= fz)
        {
            maxv = v;
            flag = i;
            gw = w;

        }
    }
    printf("重量：\t");
    for(i = 0;i < n;i++)
    {
    	printf("%-5d",a[i][0]);
	}
    puts("");
    
    printf("价值：\t");
    for(i = 0;i < n;i++)
    {
    	printf("%-5d",a[i][1]);
	}
    puts("");
    
    printf("组合：\t");
    for(i = 0;i < n;i++)
    {
    	printf("%-5d",ls[flag][i]);
	}
    printf("\n最佳重量：%d，最大价值：%d",gw,maxv);
    
    return 0;
}

---

运行结果示例

1.5个物品，负重15

数据：
5 15
12 4
2 2
1 1
4 10
1 2

2.20个物品，负重200

数据：
20 200
24 50
42 60
20 49
7 15
48 115
4 11
3 8
7 5
52 66
50 25
5 8
9 25
14 40
9 22
55 42
40 30
35 49
33 16
12 12
65 127

---

------------------------------------------------------第九次发项目类文章有点激动啊！-----------------------------------------------------
-----------------------------------------------------【C语言—微项目—自编练习】----------------------------------------------------------
----------------------------------------------------------------【TDTX】--------------------------------------------------------------------