nyoj 860 又见01背包 【另类01背包】

分析：

首先这道题不能当做普通的01背包问题，因为W <= 10^9，开不了，那么大的数组，肯定有其他的思路，观察一下我们知道价值v小的很，最大100， 那我们就可以利用这一点，拿价值 之和作为原来的质量之和， 但是有一点要注意：因为题意是要在质量不超过W的范围内，找出最大的价值，我们现在是以最大的价值求质量，那么仔细分析一下，我们就能想明白，要以某价值i的背包存放尽量小的质量，这样反过来分析一下就可以知道，较小的质量有个较大的价值序号，这样完全满足题意了， 最后还有一点，就是价值背包的每一个（出去dp【0】）都要初始化为一个比较大的数，这样就可以放最小的价值了，如果初始化为0，肯定是错的（这点仔细想一下），这点就是将背包完全填满差不多，只不过一个是负无穷罢了。。。（为甚么会这样，因为我们是反着求得）

题目链接 http://acm.nyist.net/JudgeOnline/problem.php?pid=860

代码：

#include<stdio.h>
#include<string.h>
#define MAXN 0x3f3f3f3f
typedef struct{
	int w, v;
}str;
str s[105];
int dp[10050];
int main()
{
	int n, m;
	while(scanf("%d%d", &n, &m) == 2){
		//memset(dp, 'b', sizeof(dp));  这处跟下面的作用一样 但不知道为什么
		int sum = 0;
		for(int i = 0; i < n; i ++)
			scanf("%d%d", &s[i].w, &s[i].v),
			sum+=s[i].v;
			for(int i = 0; i <= sum; i ++) dp[i] = MAXN; //跟上面的作用一样
			dp[0] = 0;
		for(int i = 0; i < n; i ++)
			for(int j = sum; j >= s[i].v; j --){
				if(dp[j] > dp[j-s[i].v]+s[i].w) dp[j] = dp[j-s[i].v]+s[i].w;
			}
			for(int i = sum; i >=0; i --)
			if(dp[i]<= m){
				printf("%d\n", i);
				break;
			}
	}
	return 0;
} 

nyoj 860 又见01背包 【另类01背包】,布布扣,bubuko.com

nyoj 860 又见01背包 【另类01背包】

原文：http://blog.csdn.net/shengweisong/article/details/38345473