# include<iostream> # include<vector> # include<memory.h> # include<cstdio> //01背包 using namespace std; int dp[10010]; int volume[10010],value[10010]; int n,v; void ZeroOnepack(int val,int vol){ for(int i = v; i >= vol; i--){ dp[i] = max(dp[i], dp[i - vol] + val); } } int main(){ //sb地方,一定要循环 while(cin>>n>>v){ memset(dp,0,sizeof(dp)); for(int k = 0; k < n; k++){ cin>>volume[k]>>value[k]; } for(int k = 0; k < n; k++){ ZeroOnepack(value[k],volume[k]); } cout<<dp[v]<<endl; } return 0; } |
Double click to view unformatted code.