Codeforces 364B 双肩包+贪心

Codeforces 364B 背包+贪心

题目链接：http://codeforces.com/problemset/problem/364/B

给定n个物品（每个物品只有1件，d值）

每次可以用手头的物品（设价值为val）换取不在手头的物品（任意件数，总价值要<=val+d)

问能换到的最大价值及在此价值下的最小次数。

思路：

先背包一下跑出所有可能换到的价值，然后贪心一直增加价值直到不能增加。

证明贪心：

对于当前集合x，要变成集合y

首先: (x)+d >= y

那么并不需要关心集合 x,y 是否有交集

如果有交集z，则z这个集合不参与更换即可，因为z换z没啥意义，也不合法。

那么剩下的就是x的 x' 换成 y的y'，显然 x'∩y' = 空集

所以贪心地增加价值合法。

#include<stdio.h>
#include<iostream>
#include<string.h>
#include<algorithm>
#include<vector>
#include<set>
using namespace std;
#define N 1234567

#define ll __int64
ll n,d;
ll a[55];
ll dp[N];
int main(){
	ll i, j;
	while(~scanf("%I64d %I64d",&n,&d)){
		memset(dp, 0, sizeof dp);
		ll sum = 0;
		for(i = 1; i <= n; i++)cin>>a[i], sum+=a[i];
		dp[0] = 1;
		
		for(i = 1; i <= n; i++)
		{
			for(j = N-a[i]-1; j>=0; j--)
			{
				if(dp[j])
					dp[j+a[i]] = 1;
			}
		}
		ll ans = 0, step = 0;
		while(1){
			for(j=ans+d;j>ans;j--)
				if(j<=sum&&dp[j])
					break;
			if(j==ans)break;
			ans = j;step++;
		}
		cout<<ans<<" "<<step<<endl;
	}
	return 0;
}