#include<bits/stdc++.h> using namespace std; int w[31],v[31]; int dp[205]; int main(){ cin>>w[0]>>v[0]; for(int i=1;i<=v[0];i++){ cin>>w[i]>>v[i]; } for(int i=1;i<=v[0];i++){ for(int j=w[i];j<=w[0];j++){ dp[j]=max(dp[j],dp[j-w[i]]+v[i]); } } cout<<dp[w[0]]; return 0; }

OK，一道完全背包的题目，套公式就行——

#include<bits/stdc++.h> using namespace std; #define MAX 1001 int n,weight; int w[MAX],v[MAX]; int dp[MAX][MAX]; int f(int n, int weight){ if(n==1){ if(weight>=w[1])return v[1](weight/w[1]); else return 0; } if(dp[n][weight]>0) return dp[n][weight]; if(weight<w[n]) dp[n][weight]=f(n-1,weight); else{ dp[n][weight]=f(n-1,weight); for(int i=1;iw[n]<=weight;i++) dp[n][weight]=max(dp[n][weight],f(n-1,weight-i*w[n])+v[n]*i); } return dp[n][weight]; }int main(){ scanf("%d%d",&weight,&n); for(int i=1;i<=n;i++){ scanf("%d%d",&w[i],&v[i]); } memset(dp,0,sizeof(dp)); printf("%d",f(n,weight)); return 0; }