我的英语差的不只一点点啊,题意看不完全懂,直接看别人的解题报告才把题意弄清(我很菜),但是感觉这题完全就是完全背包基础知识,只要将cost视为与weight完全相等就ok。
#include<cstdio> #include<cstring> #include<iostream> using namespace std; #define N 11 int dp[100010]; int num[N]; int a[N]; int V,n; inline int max(int x,int y) { return x>y?x:y; } void Zeroonepack(int wei,int cost) { for(int i=V; i>=cost; --i) dp[i] = max(dp[i],dp[i-cost]+wei); } void compeletpack(int wei,int cost) { for(int i=cost; i<=V; ++i) dp[i] = max(dp[i],dp[i-cost]+wei); } int main() { while(cin >> V >> n) { for(int i=1; i<=n; ++i) cin>> num[i]>> a[i];//分别用来存储数量及面值。 for(int i=0; i<=V; ++i) dp[i] = 0; for(int i=1; i<=n; ++i) { if(a[i]*num[i]>=V) compeletpack(a[i],a[i]); else { int k=1; while(k<num[i]) { num[i] -= k; Zeroonepack(a[i]*k,a[i]*k); k += k; } } Zeroonepack(a[i]*num[i],a[i]*num[i]); } int ma = 0; for(int i=1; i<=V; ++i) if(ma < dp[i]) ma = dp[i]; cout << ma <<endl; } return 0; }