題目鏈接

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

這題是我的0-1背包開山第一題 對于0-1背包還不是很理解：

?

0-1背包的一幫形式

int dp[MAX_W+1]//DP數組

void solve()
{
for(int i=0;i<n;i++)
{
for(int j=w;j>=w[i];j--)
{
dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
}
}
printf("%d\n",dp[w]);
}

?

對于0-1背包我的理解，其實0-1背包就是遞歸的變化；

?

對于這個題目就是0-1背包 ?但是要有一點小小的變換 ?就是 要想 使卡里的錢最少 我先預留5 元 到最后去買最貴的菜，用m-5 進行0-1背包

代碼

#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
using namespace std;

int main(void)
{
int i,j,k,n,m;
int price[1010];
int dp[1010];
while(scanf("%d",&n)==1&&n)
{
memset(dp,0,sizeof(dp));
for(i=1;i<=n;i++)
scanf("%d",price+i);
scanf("%d",&m);
if(m<5)
{
printf("%d\n",m);
continue;
}
m=m-5;
sort(price+1,price+n+1);
int Max=price[n];
for(i=1;i<n;i++)
{
for(j=m;j>=price[i];j--)
{
dp[j]=max(dp[j],dp[j-price[i]]+price[i]);
}
}
printf("%d\n",m+5-dp[m]-Max);
}
return 0;
}

?

這是一個很好的0-1背包題

轉載于:https://www.cnblogs.com/liudehao/p/4093609.html

總結

以上是生活随笔為你收集整理的HDU-2546-饭卡的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。