饭卡（01背包）

本文主要是介绍饭卡（01背包），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意：

这是一个经典的01背包问题，但此问题处理起来却需要小技巧，对我来说算是比较新颖，需要加一个限制，那就是余额要大于等于5，要注意的是这里只要剩余的钱不低于5元，就可以购买任何一件物品，所以5在这道题中是很特殊的，在使用01背包之前，我们首先要在现在所拥有的余额中保留5元，用这五元去购买最贵的物品（此处默认最贵的比5元贵了），而剩下的钱就是背包的总容量，可以随意使用！

代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <string>
#include <map>
#include <stack>
#include <vector>
#include <set>
#include <queue>
#include <iomanip>
#define maxn 15
#define MAXN 100005
#define mod 1000000007
#define INF 0x3f3f3f3f
#define exp 1e-6
#define pi acos(-1.0)
using namespace std;
int main()
{//freopen("D:\\a.txt","r",stdin);ios::sync_with_stdio(false);int n,m,i,j,max1;int price[1001],dp[1001];while(cin>>n,n){max1=-1;memset(price,0,sizeof(price));memset(dp,0,sizeof(dp));for(i=1;i<=n;i++){cin>>price[i];}sort(price+1,price+n+1);max1=price[n];   //找出价格最大的那个，用五元钱去买，剩余的就是01背包问题cin>>m;if(m<5){cout<<m<<endl;continue;}m=m-5;for(i=0;i<n;i++)for(j=m;j>=price[i];j--){dp[j]=max(dp[j],dp[j-price[i]]+price[i]);}cout<<m+5-dp[m]-max1<<endl;}return 0;
}

这篇关于饭卡（01背包）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---