二維費用的背包問題是背包問題的一個簡單的常見擴展，
二維費用的背包問題的一般描述為：對于裝入背包的每個物品i，都具有兩種不同的代價 C1[i]與C2[i]，選擇物品i裝入背包時必須同時付出這兩種代價；對于每種代價都有一個可付出的最大值（上限）V1和V2，物品i裝入可獲得的價值為P[i]，問在每個物品只能裝入一次的條件下，怎么選擇物品可得到最大的價值，
其解題思路一般為：
令 f[i][j][k]表示前i個物品在代價1為j，代價2為k的條件下裝入背包的可獲得的最大值，
根據0/1背包問題有
f[i][j][k] = max { f[i?1][j][k] , f[i?1][j?C1[i]][k?C2[i]] + P[i]}
同樣可以將陣列由三維陣列優化為二維陣列，即
f[j][k] = max { f[j][k] , f[j?C1[i]][k?C2[i]] + P[i]}
撰寫代碼時，一般采用如下的3重回圈：
? for (i=1;i<=n;i++) // 裝入背包的物品個數為n
for (j=V1;j>=C1[i];j--)
for (k=V2;k>=C2[i];k--)
{
f[j][k]=max(f[j][k],f[j-C1[i]][k-C2[i]]+P[i]);
}
所求最大價值為f[V1][V2]，
【例1】游戲專案
問題描述
一天小明來到歡歡娛樂城游玩，游樂場的游戲專案真多呀，每個游戲專案需要花費小明的一些時間和一些金錢，
由于小明的時間和金錢是有限的，所以他很難將所有游戲專案都玩一遍，他決定選擇一些專案進行游玩，并且每個專案最多玩一次，他想知道在不超過自己所剩時間和金錢的范圍內，最多可以玩多少個游戲專案？
輸入
第一行三個整數n,M,T，表示一共有n（1≤n≤100）個游戲專案， 小明的手上還剩M（0≤M≤200）元，他有T（0≤T≤200）分鐘時間，
第2~n+1行 mi, ti 表示玩第i個游戲專案所需要的金錢和時間，
輸出
一行，一個數，表示小明最多可以玩的游戲專案的個數，
輸入樣例
6 10 10
1 1
2 3
3 2
2 5
5 2
4 3
輸出樣例
4
（1）編程思路，
玩游戲專案i時，需要付出的兩種代價分別為時間t[i]和金錢m[i]，直接套用二維費用背包問題的模板即可，
（2）源程式，
#include <stdio.h> int max(int a,int b) { if (a>b) return a; else return b; } int main() { int f[205][205]={0}; int m[101],t[101]; int n,M,T; scanf("%d%d%d",&n,&M,&T); int i,j,k; for (i=1;i<=n;i++) { scanf("%d%d",&m[i],&t[i]); } for (i=1;i<=n;i++) for (j=M;j>=m[i];j--) for (k=T;k>=t[i];k--) { f[j][k]=max(f[j][k],f[j-m[i]][k-t[i]]+1); } printf("%d\n",f[M][T]); return 0; }
【例2】L國的戰斗之間諜
問題描述
L國即將與I國發動戰爭！！L國的指揮官想派出間諜前往I國，于是，選人作業就落到了你身上，
你現在有N個人選，每個人都有這樣一些資料：A（能得到多少資料）、B（偽裝能力有多差）、C（要多少工資），已知敵人的探查間諜能力為M（即去的所有人B的和要小于等于M）和手頭有X元錢，請問能拿到多少資料？
輸入
輸入第1行為三個整數：N、M、X（1≤N≤100，1≤M≤1000，1≤X≤1000），
之后有N行，每行包括三個整數：Ai、Bi、Ci，表示第i個人選相關資料，
輸出
能得到的資料總數，
輸入樣例
3 10 12
10 1 11
1 9 1
7 10 12
輸出樣例
11
（1）編程思路，
選擇第i個人選時，需要付出的兩種代價分別為偽裝能力b[i]和需要的經費c[i]，選擇該人選后，可獲得的資料為a[i]，直接套用二維費用背包問題的模板即可，
（2）源程式，
#include <stdio.h> int f[1001][1001]={0}; int main() { int n,m,x; scanf("%d%d%d",&n,&m,&x); int a[101],b[101],c[101]; int i,j,k; for (i=1;i<=n;i++) scanf("%d%d%d",&a[i],&b[i],&c[i]); for (i=1;i<=n;i++) { for (j=m;j>=b[i];j--) for (k=x;k>=c[i];k--) if (f[j][k]<f[j-b[i]][k-c[i]]+a[i]) f[j][k]=f[j-b[i]][k-c[i]]+a[i]; } printf("%d\n",f[m][x]); return 0; }
將上面的源程式提交給洛谷題庫P1910 L國的戰斗之間諜（https://www.luogu.com.cn/problem/P1910），測評結果為“Accepted”，
【例3】三角牧場
問題描述
奶牛牧場建筑師I.M.Hei負責創建一個三角形的牧場，周圍有漂亮的白色圍欄，她被提供了N（3<=N<=40）個圍欄段，每個圍欄段的長度為整數Li（1<=Li<=40），她用這些圍欄段來組成三角形牧場的三條邊，使得該牧場的放牧面積最大，
輸入
第1行：單個整數N
第2行~N+1行：每行都有一個整數，表示一個圍欄段的長度，長度不一定是唯一的，
輸出
輸出一行為一個整數，該整數是最大可能封閉區域的面積乘以100的截斷整數表示，如果不能圍成三角形，則輸出-1，
輸入樣例
5
1
1
3
3
4
輸出樣例
692
（1）編程思路，
把邊的長度看成費用，三角形中的某條邊i看作第一維費用，另一條邊j看作是第二維費用，背包容量為總長sum的一半（三角形任意一條邊都不可能比周長的一半大），則第三邊為sum-i-j，給定的圍欄看成裝入背包的物品，
設f[i][j]表示由這些圍欄是否可以構成一條邊長為i，另一條邊長為j，初始時除f[0][0]=1外，其余元素全部為0，
通過二維0/1背包找出所有滿足的i,j（即f[i][j]=1），列舉求出最大面積即可，
（2）源程式，
#include <stdio.h> #include <string.h> #include <math.h> int f[805][805]; int main() { int len[45]; int n; while (scanf("%d",&n) !=EOF) { int sum=0; int i,j,k; for (i=1; i<=n; i++) { scanf("%d",&len[i]); sum+=len[i]; } memset(f,0,sizeof(f)); f[0][0]=1; int mid=sum/2; for (i=1; i<=n; i++) for (j=mid; j>=0; j--) for (k=mid; k>=0; k--) { if ((j>=len[i]&& f[j-len[i]][k])||(k>=len[i]&&f[j][k-len[i]])) f[j][k]=1; } int ans=-1; for (i=mid; i>0; i--) // 通過列舉可構成三角形的兩條邊，找到最大面積 for (j=mid; j>0; j--) if (f[i][j]) { k=sum-i-j; // 第3條邊的長度 if (i+j>k && i+k>j && j+k>i) // 兩邊之和大于第三邊 { double p=sum/2.0; double x=sqrt(p*(p-i)*(p-j)*(p-k)); if (x*100>ans) ans=x*100; } } printf("%d\n",ans); } return 0; }
將上面的源程式提交給北大OJ題庫POJ 1948 Triangular Pastures（http://poj.org/problem?id=1948），可以Accepted，
【例4】鋪放線段
問題描述
有n條線段，每條線段只能放在數軸上的一個特定位置，并且第i根線段有如下幾個屬性：Xi（該線段放在數軸上的起點），Wi（該線段長度），Fi（你若使用該線段你能獲得的價值），Ci（你若使用該線段你所需要的費用），現在讓你從中選出一些線段，使得這些線段能夠鋪滿數軸上的區間[0,L]，并且所花費用和不超過B，同時要使你識訓的價值盡量大，請你找到這個方案，
輸入
第一行三個整數 L（1 ≤L≤1,000），n（1≤N≤10,000），B（1 ≤B≤1,000），
接下來n行，每行四個整數 Xi，Wi，Fi，Ci，表示第i根線段的四個屬性，
輸出
一個整數，表示你能獲得的最大價值和，若無法滿足上述要求，則輸出?1，
輸入樣例
5 6 10
0 2 20 6
2 3 5 6
0 1 2 1
1 1 1 3
1 2 5 4
3 2 10 2
輸出樣例
17
（1）編程思路，
設f[i][j]表示選出的線段鋪滿數軸上的區間[0,i]且所花費用和不超過j時能識訓的最大價值，由于要鋪滿數軸上的區間[0,L]，也就是背包的第1維得裝滿，因此初始時除f[0][0]=0外，其余元素均置為-1，f[i][j]=-1時，表示要鋪滿[0,i]區間不可能，因此，轉移是要保證轉移前的f[i’][j’]>=0，
另外，需要對給定線段其放在數軸上的起點從小到大排個序，
（2）源程式，
#include <stdio.h> #include <string.h> #include <algorithm> using namespace std; int f[1005][1005]; struct Node { int x,y,f,c; }; int cmp(struct Node a,struct Node b) { return a.x<b.x; } int max(int a,int b) { return a>b?a:b; } int main() { memset(f,-1,sizeof(f)); f[0][0]=0; int L,n,B; scanf("%d%d%d",&L,&n,&B); struct Node a[10005]; int i,j; for (i=1;i<=n;i++) { scanf("%d%d%d%d",&a[i].x,&a[i].y,&a[i].f,&a[i].c); a[i].y+=a[i].x; } sort(a+1,a+n+1,cmp); for (i=1;i<=n;i++) { for (j=B;j>=a[i].c;j--){ if(f[a[i].x][j-a[i].c]>=0) { f[a[i].y][j]=max(f[a[i].y][j],f[a[i].x][j-a[i].c]+a[i].f); } } } int ans=-1; for (i=1;i<=B;i++) ans=max(ans,f[L][i]); printf("%d",ans); return 0; }
將上面的源程式提交給洛谷題庫P2854 [USACO06DEC]Cow Roller Coaster S（https://www.luogu.com.cn/problem/P2854），測評結果為“Accepted”，
【例5】寵物小精靈之收服
問題描述
寵物小精靈是一部講述小智和他的搭檔皮卡丘一起冒險的故事，
一天，小智和皮卡丘來到了小精靈狩獵場，里面有很多珍貴的野生寵物小精靈，小智也想收服其中的一些小精靈，然而，野生的小精靈并不那么容易被收服，對于每一個野生小精靈而言，小智可能需要使用很多個精靈球才能收服它，而在收服程序中，野生小精靈也會對皮卡丘造成一定的傷害（從而減少皮卡丘的體力），當皮卡丘的體力小于等于0時，小智就必須結束狩獵（因為他需要給皮卡丘療傷），而使得皮卡丘體力小于等于0的野生小精靈也不會被小智收服，當小智的精靈球用完時，狩獵也宣告結束，
我們假設小智遇到野生小精靈時有兩個選擇：收服它，或者離開它，如果小智選擇了收服，那么一定會扔出能夠收服該小精靈的精靈球，而皮卡丘也一定會受到相應的傷害；如果選擇離開它，那么小智不會損失精靈球，皮卡丘也不會損失體力，
小智的目標有兩個：主要目標是收服盡可能多的野生小精靈；如果可以收服的小精靈數量一樣，小智希望皮卡丘受到的傷害越小（剩余體力越大），因為他們還要繼續冒險，
現在已知小智的精靈球數量和皮卡丘的初始體力，已知每一個小精靈需要的用于收服的精靈球數目和它在被收服程序中會對皮卡丘造成的傷害數目，請問，小智該如何選擇收服哪些小精靈以達到他的目標呢？
輸入
輸入資料的第一行包含三個整數：N(0 < N < 1000)，M(0 < M < 500)，K(0 < K < 100)，分別代表小智的精靈球數量、皮卡丘初始的體力值、野生小精靈的數量，
之后的K行，每一行代表一個野生小精靈，包括兩個整數：收服該小精靈需要的精靈球的數量，以及收服程序中對皮卡丘造成的傷害，
輸出
輸出為一行，包含兩個整數：C，R，分別表示最多收服C個小精靈，以及收服C個小精靈時皮卡丘的剩余體力值最多為R，
樣例輸入
輸入樣例
10 100 5
7 10
2 40
2 50
1 20
4 20
輸出樣例
3 30
（1）編程思路，
若收服某個小精靈需要的精靈球的數量超過了小智的精靈球數量或者收服程序中對皮卡丘造成的傷害超過了皮卡丘初始的體力值，則該小精靈不可能被收服，輸入時對資料進行預處理，將不可能收服的小精靈忽略掉，只保存可能收服的小精靈，
設f[i][j]表示扔i個精靈球且皮卡丘損失j體力時所能抓到的最大精靈數，初始值全部為0，用二維費用的0/1背包進行處理，
最后按皮卡丘損失體力從小到大回圈處理陣列元素f[n][1]~f[n][m]，找到這些元素中的最大值f[n][i]，此時m-i就是皮卡丘剩余體力的最大值，
（2）源程式，
#include <stdio.h> #include <string.h> int max(int a,int b) { return a>b?a:b; } int f[1005][505]={0}; int main() { int n,m,t; scanf("%d%d%d",&n,&m,&t); int num=0; int w[102],v[102]; while (t--) { int x,y; scanf("%d%d",&x,&y); if (x>n || y>=m) // 不可能收服的小精靈 continue; w[++num]=x; v[num]=y; } int i,j,k; for (i=1;i<=num;i++) for (j=n;j>=w[i];j--) for (k=m-1;k>=v[i];k--) f[j][k]=max(f[j][k],f[j-w[i]][k-v[i]]+1); int ans=0; for (i=1;i<m;i++) if (f[n][i]>f[n][ans]) ans=i; printf("%d %d\n",f[n][ans],m-ans); return 0; }
上面的5個例題中，均是二維費用的0/1背包問題，實際上，若裝入背包中的物品可以裝入無數次，就是二維費用的完全背包問題了，
【例6】FATE游戲
問題描述
最近xhd正在玩一款叫做FATE的游戲，為了得到極品裝備，xhd在不停的殺怪做任務，久而久之xhd開始對殺怪產生的厭惡感，但又不得不通過殺怪來升完這最后一級，現在的問題是，xhd升掉最后一級還需n的經驗值，xhd還留有m的忍耐度，每殺一個怪xhd會得到相應的經驗，并減掉相應的忍耐度，當忍耐度降到0或者0以下時，xhd就不會玩這游戲，xhd還說了他最多只殺s只怪，請問他能升掉這最后一級嗎？
輸入
輸入資料有多組，對于每組資料第一行輸入n，m，k，s(0 < n,m,k,s < 100)四個正整數，分別表示還需的經驗值，保留的忍耐度，怪的種數和最多的殺怪數，接下來輸入k行資料，每行資料輸入兩個正整數a，b(0 < a,b < 20)；分別表示殺掉一只這種怪xhd會得到的經驗值和會減掉的忍耐度，(每種怪都有無數個)
輸出
輸出升完這級還能保留的最大忍耐度，如果無法升完這級輸出-1，
輸入樣例
10 10 1 10
1 1
10 10 1 9
1 1
9 10 2 10
1 1
2 2
輸出樣例
0
-1
1
（1）編程思路，
由于每種怪都有無數個，而升級需要n經驗值，只殺掉s只怪，二維費用的完全背包問題，
設f[i][j]表示減掉忍耐度i且殺掉j只怪可得到的最大經驗值，
采用二維費用完全背包處理后，若f[m][s]>=n，則可以升級，對陣列f按第1維下標（忍耐度）從小到大搜索，若某個f[i][j]>=n，則i值就是可升級時減掉的最小忍耐度，m-i就是還能保留的最大忍耐度；若f[m][s]<n，則無法升級，
（2）源程式，
#include <stdio.h> #include <string.h> int max(int a,int b) { return a>b?a:b; } int f[105][105]; int main() { int n,m,k,s; while (scanf("%d%d%d%d",&n,&m,&k,&s)!=EOF) { memset(f,0,sizeof(f)); int i,j,p; for (i=1;i<=k;i++) { int a,b; scanf("%d%d",&a,&b); for (j=b;j<=m;j++) // 忍耐度 { for (p=1;p<=s;p++) // 個數限制 { f[j][p]=max(f[j][p],f[j-b][p-1]+a); } } } if (f[m][s]>=n) { for (i=1;i<=m;i++) { for (j=1;j<=s;j++) if (f[i][j]>=n) break; if (j<=s) break; } printf("%d\n",m-i); } else printf("-1\n"); } return 0; }
將上面的源程式提交給HDU OJ題庫HDU 2159 FATE（http://acm.hdu.edu.cn/showproblem.php?pid=2159），測評結果為“Accepted”，
除了上面介紹的二維費用外，有些問題可能涉及更多的費用，比如，有三個方面的費用，
【例7】買年貨
問題描述
春節將至，小明要去超市購置年貨，于是小明去了自己經常去的都尚超市，
剛到超市，小明就發現超市門口貼了一張通知，內容如下：
值此新春佳節來臨之際，為了回饋廣大顧客的支持和厚愛，特舉行春節大酬賓、優惠大放送活動，凡是都尚會員都可用會員積分兌換商品，凡是都尚會員都可免費拿k件商品，凡是購物顧客均有好禮相送，滿100元送bla bla bla bla，滿200元送bla bla bla bla bla...blablabla....
還沒看完通知，小明就高興的要死，因為他就是都尚的會員啊，迫不及待的小明在超市逛了一圈發現超市里有n件他想要的商品，小明順便對這n件商品打了分，表示商品的實際價值，小明發現身上帶了v1的人民幣，會員卡里面有v2的積分，他想知道他最多能買多大價值的商品，
由于小明想要的商品實在太多了，他算了半天頭都疼了也沒算出來，所以請你這位聰明的程式員來幫幫他吧，
輸入
輸入包含多組測驗用例，
每組資料的第一行是四個整數n，v1，v2，k；
然后是n行，每行三個整數a，b，val，分別表示每個商品的價錢，兌換所需積分，實際價值，
[Technical Specification]
1 <= n <= 100
0 <= v1, v2 <= 100
0 <= k <= 5
0 <= a, b, val <= 100
Ps. 只要錢或者積分滿足購買一件商品的要求，那么就可以買下這件商品，
輸出
對于每組資料，輸出能買的最大價值，
輸入樣例
5 1 6 1
4 3 3
0 3 2
2 3 3
3 3 2
1 0 2
4 2 5 0
0 1 0
4 4 1
3 3 4
3 4 4
輸出樣例
12
4
（1）編程思路，
每件商品可以用3種方式獲得，用錢買、用積分兌換或者用免費拿的次數免費拿，這樣涉及3個方面的費用，設f[i][j][k]表示用i元錢買，用j個積分換，免費拿k件可獲得的最大價值，就是一個3維費用的背包問題了，可用4重回圈進行處理，
（2）源程式，
#include <stdio.h> #include <string.h> int max(int a,int b) { return a>b?a:b; } int f[105][105][6]; // f[i][j][k]表示用i元錢買，用j個積分換，免費拿k件可獲得的最大價值 int main() { int a[105],b[105],v[105]; int n,v1,v2,k; while (scanf("%d%d%d%d",&n,&v1,&v2,&k)!=EOF) { int i,x1,x2,x3; for (i=1;i<=n;i++) scanf("%d%d%d",&a[i],&b[i],&v[i]); memset(f, 0,sizeof(f)); int ans = 0; for (i=1;i<=n;i++) for (x1 = v1;x1>=0;x1--) for (x2=v2;x2>=0;x2--) for (x3=k;x3>=0;x3--) { int tmp = 0; if (x1 >=a[i]) // 有錢，用錢買 tmp = max(tmp,f[x1-a[i]][x2][x3]+v[i]); if (x2 >=b[i]) // 有積分，用積分兌換 tmp=max(tmp,f[x1][x2-b[i]][x3] + v[i]); if (x3>0) // 可以免費拿，不拿白不拿 tmp=max(tmp,f[x1][x2][x3-1]+v[i]); f[x1][x2][x3]=max(f[x1][x2][x3],tmp); } printf("%d\n",f[v1][v2][k]); } return 0; }
將上面的源程式提交給HDU OJ題庫HDU 4501小明系列故事——買年貨（http://acm.hdu.edu.cn/showproblem.php?pid=4501），測評結果為“Accepted”，
練習題
1．P1507 NASA的食物計劃（https://www.luogu.com.cn/problem/P1507）
#include <stdio.h> int main() { int v,m; scanf("%d%d",&v,&m); int n; scanf("%d",&n); int a[51],b[51],c[51]; int f[401][401]={0}; int i,j,k; for (i=1;i<=n;i++) scanf("%d%d%d",&a[i],&b[i],&c[i]); for (i=1;i<=n;i++) { for(j=v;j>=a[i];j--) for (k=m;k>=b[i];k--) { if (f[j][k]<f[j-a[i]][k-b[i]]+c[i]) f[j][k]=f[j-a[i]][k-b[i]]+c[i]; } } printf("%d\n",f[v][m]); return 0; }View Code
2．P1759 通天之潛水（https://www.luogu.com.cn/problem/P1759）
#include <stdio.h> #include <string.h> struct Node { int sum; // 停留的總時間 int ans[101]; // 保存選中的數，其中a[0]是選中的數的個數 }; struct Node f[201][201]; int main() { int m,v,n; scanf("%d%d%d",&m,&v,&n); int a[101],b[101],c[101]; int i,j,k,l; for (i=1;i<=n;i++) scanf("%d%d%d",&a[i],&b[i],&c[i]); memset(f,0,sizeof(f)); for (i=1;i<=n;i++) for (j=m;j>=a[i];j--) for (k=v;k>=b[i];k--) { if (f[j-a[i]][k-b[i]].sum+c[i]>f[j][k].sum) { f[j][k].sum=f[j-a[i]][k-b[i]].sum+c[i]; for (l=1;l<=f[j][k].ans[0];l++) f[j][k].ans[l]=0; f[j][k].ans[0]=f[j-a[i]][k-b[i]].ans[0]+1; for (l=1;l<=f[j-a[i]][k-b[i]].ans[0];l++) f[j][k].ans[l]=f[j-a[i]][k-b[i]].ans[l]; f[j][k].ans[f[j][k].ans[0]]=i; // 選中i } } printf("%d\n",f[m][v].sum); for (i=1;i<=f[m][v].ans[0];i++) printf("%d ",f[m][v].ans[i]); printf("\n"); return 0; }View Code
3．POJ2576 Tug of War（http://poj.org/problem?id=2576）
#include <stdio.h> int max(int a,int b) { return a>b?a:b; } int abs(int a) { return a>0?a:-a; } int f[101][45001]={0}; int main() { int n; scanf("%d",&n); int w[101]; int total=0; int i,j,k; for (i= 1;i<=n; i++) { scanf("%d",&w[i]); total += w[i]; } f[0][0] = 1; for (i = 1; i <= n; i ++) for (j = total; j >= w[i]; j --) for (k = 1; k <= n/2 ; k ++) if (f[k - 1][j - w[i]] == 1) f[k][j] = 1; int ans = 1000000; int index = -1; for (i = total; i >= 0; i --) if (f[n / 2][i] == 1 && abs(i * 2 - total) < ans) { ans = abs(i * 2 - total); index = i; } if (index <= total / 2) printf("%d %d\n",index,total - index); else printf("%d %d\n",total - index,index); return 0; }View Code
4．HDU 3127 WHUgirls（http://acm.hdu.edu.cn/showproblem.php?pid=3127）
#include <stdio.h> #include <string.h> int max(int a,int b) { return a>b?a:b; } int f[1005][1005]; int main() { int t; scanf("%d",&t); while (t--) { int n,X,Y; scanf("%d%d%d",&n,&X,&Y); memset(f,0,sizeof(f)); int x[20],y[20],value[20]; int i,j,k; for (i=1; i<=n; i++) scanf("%d%d%d",&x[i],&y[i],&value[i]); for (i=0; i<=X; i++) for (j=0; j<=Y; j++) for (k=1; k<=n; k++) { if (i>=x[k] && j>=y[k]) // 第一種情況 f[i][j]=max(f[i][j],max(f[x[k]][j-y[k]]+f[i-x[k]][j],f[i-x[k]][y[k]]+f[i][j-y[k]])+value[k]); if (i>=y[k]&& j>=x[k]) // 第二種情況 f[i][j] = max(f[i][j],max(f[i][j-x[k]]+f[i-y[k]][x[k]],f[i-y[k]][j]+f[y[k]][j-x[k]])+value[k]); } printf("%d\n",f[X][Y]); } return 0; }View Code
5．HDU 3496 Watch The Movie（http://acm.hdu.edu.cn/showproblem.php?pid=3496）
#include <stdio.h> #include <string.h> int max(int a,int b) { return a>b?a:b; } int f[105][1005]; // f[i][j]表示買下i張影碟用j時間看完獲得的最大值 int main() { int t; scanf("%d",&t); while (t--) { memset(f,-1,sizeof(f)); int n, m, l; scanf("%d%d%d",&n,&m,&l); int i,j,k; for (i=0; i<=l; i++) f[0][i] = 0; for (i=1; i<=n; i++) { int w,v; scanf("%d%d",&w,&v); for (j=m; j>=1; j--) { for (k=l; k>=w; k--) { if (f[j-1][k-w]!=-1) { f[j][k] = max(f[j][k], f[j-1][k-w] + v); } } } } printf("%d\n",(f[m][l]==-1?0:f[m][l])); } return 0; }View Code
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/456962.html
標籤：C
上一篇：職工管理系統（代碼回顧1）