当前位置 博文首页 > Keven_11的博客:计蒜客——《饭卡》
?
01?背包 + 贪心
本题是对背包的巧妙应用,只有理解了背包才能轻松的做出这道题目。
排序后,把前?n-1?个物品计算?01?背包,计算出背包最大可以装多少价值的物品。最后加上最大的物品的价值就可以了。
#include<bits/stdc++.h>
using namespace std;
int a[1006],dp[2056];
int main(){
freopen("card.in","r",stdin);
freopen("card.out","w",stdout);
int n,m;
cin>>n;
for (int i=0;i<n;i++){
cin>>a[i];
}
cin>>m;
int mx=0;
dp[0]=1;
sort(a,a+n);
for (int i=0;i<n;i++){
for (int j=m-5;j>=0;j--){
if (dp[j]){
dp[j+a[i]]=1;
mx=max(mx,j+a[i]);
}
}
}
cout<<m-mx;
return 0;
}
/*
f数组就是dp数组,只不过是一维的
其实就是反过来考虑,因为我们数组的下标不能是负数 所以f[i]意义是总价值位i的物品能不能买
从m-5开始更新是因为少于5就不能买了
因此从m-5开始往下更新。剩下的状态都可以随意超过m,因为可以透支
j表示已经买了多少价值的饭
j+a[i]表示已经买了j,还要买a[i]得到的总价值
0是什么都不买的情况
就是dp的初始状态
其他买不买是要算出来,由dp公式转移得到
开始只能从dp[0]开始转移
*/
?
cs