程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C >> 關於C >> Hdu 2546 飯卡(DP_背包)

Hdu 2546 飯卡(DP_背包)

編輯:關於C

題目大意:電子科大的食堂刷卡問題,如果卡上余額大等於5,那就可以隨便打菜,即使打了鮑魚等價格比余額多得多的菜。現在給出n個菜的單價,每個菜買一次,問最後卡上剩的余額最少為多少?


解題思路:本題可套用01背包的思想,值是價值變為可達不可達。用dp[j]表示余額為j是否可達,可達為1,否則為0.狀態轉移方程為 if (dp[j] && j - price[i] >= 5) dp[j-price[i]] = 1;然後記錄轉移到最小值,最後輸出即可。本題有兩個地方需要注意:1、遍歷余額的順序要從0到sum,這樣轉移的時候都是利用前一次的結果,因為sum是初狀態和01背包裡的0狀態一樣。 2、price必須事先經過排序,否則前面大的先轉移到5以下,後面小的就沒辦法更新了。

 


測試數據:


3
10000 1 3
9

1
50
5

10
1 2 3 2 1 1 2 3 2 1
50

3
1 2 3
3

 

代碼:[cpp] #include <stdio.h>  
#include <string.h>  
#include <algorithm>  
using namespace std; 
#define MAX 100000  
 
 
int n,price[MAX]; 
int sum,minn,dp[MAX]; 
 
 
int main() 

    int i,j,k,t; 
 
     
    while (scanf("%d",&n) ,n) { 
 
        for (i = 1; i <= n; ++i) 
            scanf("%d",&price[i]); 
        scanf("%d",&sum); 
        sort(price+1,price+1+n); 
 
 
        memset(dp,0,sizeof(dp)); 
        dp[sum] = 1,minn = sum; 
        for (i = 1; i <= n; ++i) 
            for (j = 5; j <= sum; ++j)  
                if (dp[j] == 1)  { 
 
                    if (j - price[i] >= 5)  
                        dp[j-price[i]] = 1; 
                    if (j - price[i] < minn) 
                        minn = j - price[i]; 
                } 
 
 
        printf("%d\n",minn); 
    } 

 


摘自 ZeroClock


 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved