洛谷P1855 榨取kkksc03 01背包

洛谷的營運組決定，如果一名oier向他的教練推薦洛谷，并能夠成功的使用（成功使用的定義是：該團隊有20個或以上的成員，上傳10道以上的私有題目，布置過一次作業并成功舉辦過一次公開比賽），那麼他可以浪費掉kkksc03的一些時間的同時消耗掉kkksc03的一些金錢以滿足自己的一個願望。

Kkksc03的時間和金錢是有限的，是以他很難滿足所有同學的願望。是以他想知道在自己的能力範圍内，最多可以完成多少同學的願望？

輸入輸出格式

輸入格式：

第一行,n M T，表示一共有n(n<=100)個願望，kkksc03 的手上還剩M(M<=200)元，他的暑假有T(T<=200)分鐘時間。

第2~n+1行 mi,ti 表示第i個願望所需要的時間和金錢。

輸出格式：

一行，一個數，表示kkksc03最多可以實作願望的個數。

輸入輸出樣例

輸入樣例#1： 複制

6 10 10
1 1
2 3 
3 2
2 5
5 2
4 3
           

輸出樣例#1： 複制

4
           

說明

提示 第1,2,3,6個

思路：剛學dp，看着像01背包就瞎搞了，沒想到過了.....過了（開心），其實這是一道01背包的變形，即往一個有兩個容量的背包裡塞東西求塞的最大個數，我們假設dp[ i ][ j ][ k ]表示前 i 個願望金錢 為 j 時間為 k 最多實作願望的個數，如果

j < a[i] (第i個願望花費金錢）或 k < b[ i ] （第 i 個願望花費時間）則狀态不變即 dp[ i ][ j ][ k ] = dp[ i - 1][ j ][ k ]

否則 dp[i][j][k] = max(dp[i - 1][j][k],dp[i - 1][j - a[i]][k - b[i]] + 1)

ok，狀态轉移方程已經推出來了，就很簡單啦

代碼；

#include<bits/stdc++.h>
using namespace std;
const int maxn = 210;
int dp[105][maxn][maxn];
int a[110],b[105];
int main()
{
	int n,m,t;
	scanf("%d %d %d",&n,&m,&t);
	for (int i = 1;i <= n;i ++)
		scanf("%d %d",&a[i],&b[i]);
	for (int i = 1;i <= n;i ++)
		for (int j = 1;j <= m;j ++)
			for (int k = 1;k <= t;k ++)
				if (j < a[i] || k < b[i])
					dp[i][j][k] = dp[i - 1][j][k];
				else
					dp[i][j][k] = max(dp[i - 1][j][k],dp[i - 1][j - a[i]][k - b[i]] + 1);
	printf("%d\n",dp[n][m][t]);	
	return 0;
}