原题http://acm.hdu.edu.cn/showproblem.php?pid=2546

饭卡

Time Limit: 5000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 11331    Accepted Submission(s): 3895

1
50
5
10
1 2 3 2 1 1 2 3 2 1
50
0

-45
32

//一道很水的01背包，状态转移方程为dp[j] = max(dp[j],dp[j-cost[i]]+cost[i]);
//但在处理之前要先把5拿出来处理掉。。。
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#include <limits.h>
#include <ctype.h>
#include <math.h>
#include <string.h>
#include <string>
#include <algorithm>
#include <iostream>
#include <stack>
#include <queue>
#include <deque>
#include <vector>
#include <set>
#include <map>
using namespace std;
#define N 1000 + 10
int dp[N];
int cost[N];

int max(int a,int b){
	return a>b?a:b;
}

int main(){
	int n,i,m;
	
	while(~scanf("%d",&n)){
		if(n == 0){
			break;
		}
		memset(dp,0,sizeof(dp));
		memset(cost,0,sizeof(cost));
		for(i=1;i<=n;i++){
			scanf("%d",&cost[i]);
		}
		sort(cost,cost+n+1);
		scanf("%d",&m);
		int j;
		if(m >= 5){	
			for(i=1;i<=n-1;i++){
				for(j=m-5;j>=cost[i];j--){
					dp[j] = max(dp[j],dp[j-cost[i]]+cost[i]);
				}
			}
			printf("%d\n",m-cost[n]-dp[m-5]);
		}
		else{
			printf("%d\n",m);
		}
		//printf("%d\n",m-dp[m]);
	}
	
	return 0;
}

01背包,布布扣,bubuko.com

01背包

原文：http://blog.csdn.net/zcr_7/article/details/38467079