首页 > 代码库 > hdu 2546 饭卡

hdu 2546 饭卡

2024-07-15 04:10:58   223人阅读

 0-1背包问题

i = 1，扫所有上限价钱只购买一件物品的最大消费（price[1]）

i = 2，更新一遍，此时是购买两件物品的最大消费（price[2]）

以此类推~有n件物品

但是只进行到n-1，是因为最大的那件物品留至最后才减

价值最高上限为m-5

 1 #include<iostream> 2 #include<memory.h> 3 #include<algorithm> 4 using namespace std; 5 int price[1010]; 6 int f[1010]; 7 int main() 8 { 9     int n,m;10     while(cin>>n && n)11     {12         memset(price,0,sizeof(price));13         for(int j = 1; j <= n; j++)14             cin>>price[j];15         sort(price+1,price+n+1);16         int Max = price[n];17         cin>>m;18         if(m < 5)19         {20             cout<<m<<endl;21         }22         else23         {24             memset(f,0,sizeof(f));25             for(int i = 1; i <= n - 1; i++)26                 for(int j = m - 5; j >= price[i]; j--)27                     if(f[j] < f[j-price[i]] + price[i])//f[j]表示j元时，i件物品所需的最大值28                         f[j] = f[j-price[i]] + price[i];29             cout<<m-f[m-5]-Max<<endl;30         }31     }32     return 0;33 }

 


联系
我们