饭卡
一道01背包的题目，特殊之处在于要先拿出5元用来买最贵的东西，剩下的钱即为背包，然后就是普通的01背包了。
代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
|
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
using namespace std;
const int maxn=1005;
int pri[maxn];
int dp[maxn];
int ()
{
int n,m;
while(scanf("%d",&n)!=EOF&&n)
{
memset(pri,0,sizeof(pri));
memset(dp,0,sizeof(dp));
for(int i=1;i<=n;i++) scanf("%d",&pri[i]);
scanf("%d",&m);
if(m<5)
{
printf("%dn",m);
continue;
}
int vtot=m-5;
sort(pri+1,pri+1+n);
for(int i=1;i<n;i++)
for(int j=vtot;j>=pri[i];j--)
dp[j]=max(dp[j],dp[j-pri[i]]+pri[i]);
int ans=m-pri[n]-dp[vtot];
printf("%dn",ans);
}
return 0;
}
|
近期评论