信息学奥赛一本通T1268-完全背包问题-题解(C语言代码)

1060 阅读 1 评论 0 点赞

（1）**菜鸟级理解**
（2）**毫无算法可言**
（3) **用时间减少bug**
想敲这题也是因为那题波动数列，了解到01背包，然后就这个完全背包，说实话快废了，整个人颓废了。你们看看别人的
（所以我就发个异类出来，因为好胆也是我的心血）
这个就是有着01背包的初级想法的完全背包（01背包那种变成一维数组，用余数算，我理解不了。。。我都不知道我怎么是大学生的了）
想法：一个一个叠加；先排序，使它计算的价值越来越高；
我不知道，但我最大排序让我这个全对；因为这里面判断杂乱，排序会让他数值稳定。

#include<stdio.h>
    #include<string.h>
    #include<stdlib.h>
    int max(int x, int y) {//用于judge判断
    	if (x > y)return 1;
    	else return 0;
    }
    int maxs(int x, int y, int z) {//因为下一个一定最大的
    	if (x > y) {
    		if (x > z)return x;
    		else return z;
    	}
    	else {
    		if (y > z)return y;
    		else return z;
    	}
    }
    int main() {
    	int n, s, i, a, b, c, l = 1;
    	int list[30][200];
    	int* data[30];//存储重量和价值
    	for (i = 0; i < 30; i++) {
    		data[i] = (int*)malloc(sizeof(int) * 2);
    	}
    	memset(list, 0, sizeof(list));//使list全为0
    	scanf("%d%d", &s, &n);
    	for (i = 0; i < n; i++) {
    		scanf("%d%d", &data[i][0], &data[i][1]);
    	}
    	for (i = 0; i < n; i++) {//对价值进行升序排序
    		for (c = i + 1; c < n; c++) {
    			if (data[i][1] > data[c][1]) {
    				int* temp = data[i];
    				data[i] = data[c];
    				data[c] = temp;
    			}
    		}
    	}
    	while (n) {
    		a = data[l - 1][0];
    		b = data[l - 1][1];
    		for (i = 0; i <= s; i++) {
    			if (i >= a) {
    				c = i;
    				if (c % a == 0) {//排序好了，用倍数计算就不用判断那么多了
    					list[l][i] = maxs(list[l - 1][i], list[l][i - 1], c / a * b);
    					continue;
    				}
    				int judge=-1;
    				while (c) {
    					if (c - a < 0)break;
    					if (list[l][i] != 0) {
    						if (judge == 0)//除c外的其它空间已经被用了，如果要继续加，就要减去前面的，让这个物品的价值叠加；【2】
    							list[l][i] -= list[l - 1][c];
    						else list[l][i] = list[l][i] - list[l - 1][c + a]+b;
    					}
    					c = c - a;
    					judge = max(list[l - 1][c + a], list[l - 1][c] + b);//judge判断加的是什么【1】
    					if (judge == 0)
    						list[l][i] += list[l - 1][c] + b;
    					else list[l][i] += list[l - 1][c + a];
    				}
    				list[l][i] = maxs(list[l-1][i],list[l][i], list[l][i - 1]);
    			}
    			else list[l][i] = list[l - 1][i];
    		}
    		l++;
    		n--;
    	}
    	printf("max=%d", list[l - 1][s]);
    	for (i = 0; i < 30; i++) {//释放内存
    		free(data[i]);
    	}
    	return 0;
    }
	
就算被自己看不起，也要加油呀（笑）

0.0分

3 人评分

本文分类：题解列表
浏览次数：1060 次浏览
发布日期：2020-03-13 00:18:30
本文链接：https://blog.dotcpp.com/a/67868

上一篇 > 蓝桥杯2013年第四届真题-格子刷油漆-DFS(C++代码)
下一篇 > [编程入门]成绩评定-题解(C++代码)

C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程，并配有习题和答疑，点击了解：

一点编程也不会写的：零基础C语言学练课程

解决困扰你多年的C语言疑难杂症特性的C语言进阶课程

从零到写出一个爬虫的Python编程课程

只会语法写不出代码？手把手带你写100个编程真题的编程百练课程

信息学奥赛或C++选手的必学C++课程

蓝桥杯ACM、信息学奥赛的必学课程：算法竞赛课入门课程

手把手讲解近五年真题的蓝桥杯辅导课程

信息学奥赛一本通T1268-完全背包问题-题解(C语言代码)

评论列表共有 1 条评论

发表评论取消回复

信息学奥赛一本通T1268-完全背包问题-题解(C语言代码)

T1010-利润计算--步骤清晰

一个for循环解决问题

菲波那契数列的vector解法

慢慢看，慢慢理解，你也能做到，

评论列表 共有 1 条评论

发表评论 取消回复

评论列表共有 1 条评论

发表评论取消回复