cdoj 31 饭卡(card) 01背包

点击打开链接

思路：01背包，跑容量为m-5，物品为n-1件的01背包。贪心：用剩下的5元买最贵的

转移：dp[i][j] = max(dp[i-1][j],dp[i-1][j-c[i]]+c[i]，滚动优化一下就好了

代码:

#include <bits/stdc++.h>using namespace std;const int maxn = 1e3+10;int c[maxn],dp[50005];int main(){	int n,m;	while(cin>>n,n){		for(int i=1; i<=n; i++)			cin >> c[i];		cin >> m;		if(m<5){               cout<<m<<endl;            continue;        }		sort(c+1,c+1+n);		memset(dp,0,sizeof(dp));		for(int i=1; i<n; i++){			for(int j=m-5; j>=c[i]; j--){				dp[j] = max(dp[j],dp[j-c[i]]+c[i]);			}		}		int ans = m-(dp[m-5]+c[n]);		cout << ans << endl;	}}