时间限制: 1 s
空间限制: 16000 KB
题目等级 : 黄金 Gold
题目描述 Description
这里简直是吃货的天堂,小吃太多了。数不胜数。
假设岛上有N种小吃,每种体积Vi,美味度Wi。
设某吃货旅行者的食量C,求他能吃到食品的最大美味度。
输入描述 Input Description
两个正整数N C
N个正整数,Vi
N个正整数,Wi
输出描述 Output Description
最大美味值
样例输入 Sample Input
4 10
2 5 1 9
10 24 1 100
样例输出 Sample Output
101
数据范围及提示 Data Size & Hint
N<=100,C<=10000,Vi,Wi<=1000
可以DP,可以DFS
思路:01背包
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int n,c,w[],v[],f[];
int main()
{
cin>>n>>c;
memset(f,,sizeof f );
for(int i=;i<=n;i++) cin>>v[i];
for(int i=;i<=n;i++) cin>>w[i];// mei wei du
for(int i=;i<=n;i++)
{
for(int j=c;j>=v[i];j--)
{ f[j]=max(f[j],f[j-v[i]]+w[i]);
}
}
printf("%d",f[c]);
return ;
}