happy card
鏈接：https://ac.nowcoder.com/acm/contest/5848/G
來源：牛客網

題目描述

給你n個人，每一個人最多可以選k張牌，這n個人都喜歡數s，一張牌有一個數，如果這個數是s，則這個牌稱為happy card

每一個人拿到不同數量的happy card 可以獲得不同數量的歡樂值。

假如一個人拿到了 i 張happy card ，則可以獲得 hi 的歡樂值( hi 數組單調遞增)， 沒有happy card的人的歡樂值為0.

如果沒有拿到happy card，則獲得的歡樂值為0。

現在你需要把著n張牌分配給這n個人（每個人的牌數都可以為0），使這n個人的快樂值總和最大
輸入描述:

第一行三個數字n,k,s, 1 <= n <= 500, 1<= k <= n , 1 <= s <= 1e9

接下來n個數代表n張牌上的數ai， 1 <= ai <= 1e9

接下來k個數代表hi的值,1 <= hi <= 1e9

保證 hi-1 <= hi

輸出描述:

最大的快樂值和

分析

第一次做這道題的時候，沒有聯想到多重背包，可能就是做題做少了。

完全背包（這里是多重背包更好）是每個物品可以用s次，每個物品有花費v和價值w，問背包容量不超過V時放進來的最大價值。

對應本題
這里的“背包”是快樂卡的總數cnt
這里的“物品”是人

f(i,j)表示給第1-i個人卡片，卡片數量不超過cnt的最大價值
這里每個人不超過k張卡片

ac代碼

#include<bits/stdc++.h> using namespace std; const int maxn=550; typedef long long ll; int n,k,s;//分別表示人數(牌數),每個人最多選多少張牌，幸運數字int a;//代表卡牌上的數字 int h[maxn];//代表歡樂值，也就是物品價值 ll f[maxn][maxn];//f[i][j]表示從1-i個物品中選，每件物品不管選幾件，背包容量不超過j的最大價值//對應本題//給1-i個人快樂卡，每個人給卡個數不超過k個，快樂牌的個數不超過j的最大快樂值 int main(){cin>>n>>k>>s;int cnt=0;//統計快樂牌的個數，也就是背包容量 for(int i=0;i<n;i++){cin>>a;if(a==s) cnt++;}for(int i=1;i<=k;i++) cin>>h[i];//讀入不同數量幸運牌對應的價值memset(f,0,sizeof(f)); for(int i=1;i<=n;i++) for(int j=1;j<=cnt;j++) for(int m=1;m<=k&&m<=j;m++){//枚舉背包容量，也就是快樂牌的個數 f[i][j]=max(f[i][j],f[i-1][j-m]+h[m]);}cout<<f[n][cnt]<<endl;}

既然是多重背包，就可以對空間進行優化，此題時間上也可以優化，由于k≤n人數，最優的不是所有人手里都有牌，這樣獲得的快樂值不是最大的，這里枚舉人數的for循環給去掉，直接枚舉每個人手中的卡牌個數。

#include<bits/stdc++.h> using namespace std; const int maxn=550; typedef long long ll; int n,k,s;//分別表示人數(牌數),每個人最多選多少張牌，幸運數字int a;//代表卡牌上的數字 int h[maxn];//代表歡樂值，也就是物品價值 ll f[maxn];//f[i][j]表示從1-i個物品中選，每件物品不管選幾件，背包容量不超過j的最大價值//對應成本題//給1-i個人快樂卡，每個人給卡個數不超過k個，快樂牌的個數不超過j的最大快樂值 int main(){cin>>n>>k>>s;int cnt=0;//統計快樂牌的個數，也就是背包容量 for(int i=0;i<n;i++){cin>>a;if(a==s) cnt++;}for(int i=1;i<=k;i++) cin>>h[i];//讀入不同數量幸運牌對應的價值memset(f,0,sizeof(f)); for(int i=1;i<=k;i++)//枚舉每個人卡的個數for(int j=i;j<=cnt;j++){//枚舉背包容量f[j]=max(f[j],f[j-i]+h[i]);}cout<<f[cnt]<<endl;}

總結

以上是生活随笔為你收集整理的happy card 完全背包dp的全部內容，希望文章能夠幫你解決所遇到的問題。

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