/*
問題描述：有N件物品和一個容量為V的背包。第i件物品的費用是c[i]，價值是w[i]。求解將哪些物品裝入背包可使價值總和最大。
用子問題定義狀態：即f[i][v]表示前i件物品恰放入一個容量為v的背包可以獲得的最大價值。則其狀態轉移方程便是：
f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]}
空間優化：
for i=1..N
for v=V..0
f[v]=max{f[v],f[v-c[i]]+w[i]}; //等價於狀態轉移方程，用一維數組代替二維數組
初始化細節：
若要求恰好裝滿背包，初始化時除了f[0]為0其它f[1..V]均設為-∞
若沒有要求必須把背包裝滿，初始化時將f[0..V]全部設為0
*/
[cpp]
#include<stdio.h>
#include<string.h>
#define max(a,b) a>b?a:b
//c記錄物品費用，w記錄物品價值；
int c[3500],w[3500],f[13000];
int main()
{
int i,j,n,m;
while(scanf("%d%d",&n,&m)!=EOF){
for(i=0;i<n;i++)scanf("%d%d",&c[i],&w[i]);
memset(f,0,sizeof(f));
for(i=0;i<n;i++){ //主循環,確定物品數為i(即前i種)
for(j=m;j>=c[i];j--){ //在給定物品時，改變背包容量j
f[j]=max(f[j],f[j-c[i]]+w[i]);
}
}
printf("%d\n",f[m]);
}
return 0;
}
#include<stdio.h>
#include<string.h>
#define max(a,b) a>b?a:b
//c記錄物品費用，w記錄物品價值；
int c[3500],w[3500],f[13000];
int main()
{
int i,j,n,m;
while(scanf("%d%d",&n,&m)!=EOF){
for(i=0;i<n;i++)scanf("%d%d",&c[i],&w[i]);
memset(f,0,sizeof(f));
for(i=0;i<n;i++){ //主循環,確定物品數為i(即前i種)
for(j=m;j>=c[i];j--){ //在給定物品時，改變背包容量j
f[j]=max(f[j],f[j-c[i]]+w[i]);
}
}
printf("%d\n",f[m]);
}
return 0;
}
