“骨头收藏家”（袋子问题）（简单dp）

“骨头收藏家”（袋子问题）（简单dp）

题目：

题目大意：

一个骨头收藏家，他有一个体积为m的袋子，他去了坟墓，遇到n个骨头，每个骨头的价值和体积不一样，求他能装骨头的最大价值。

代码：

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int mm[1005][1005],a[1005],b[1005];//mm保存价值表，a保存价值，b保存体积
int main()
{int t;int n,m;scanf("%d",&t);//输入样例数量for(int i=0; i<t; i++){scanf("%d %d",&n,&m);//输入骨头数目，袋子体积for(int j=1; j<=n; j++)//输入各骨头的价值scanf("%d",&a[j]);for(int j=1; j<=n; j++)//输入各骨头的体积scanf("%d",&b[j]);int x=0,y=0;memset(mm,0,sizeof(mm));for(int i=1; i<=n; i++){for(int j=0; j<=m; j++){if(j>=b[i])/*状态转移方程：if(j>=b[i]){mm[i][j]=max(mm[i-1][j],mm[i-1][j-b[i]]+a[i])}else{mm[i][j]=mm[i-1][j]}*/mm[i][j]=max(mm[i-1][j],mm[i-1][j-b[i]]+a[i]);elsemm[i][j]=mm[i-1][j];}}printf("%dn",mm[n][m]);}return 0;
}