思路
01背包模版题，唯一不同的是加了一个条件就是价格与重要度的乘积。
转移方程为：dp[j]=max(dp[j],dp[j-w[i]]+w[i]*v[i]);
这里加了滚动数组优化。
代码
#include<bits/stdc++.h>
#define ll long long
#define ld long double
using namespace std;
inline void read(int &x) {
x=0;
short flag=1;
char c = getchar();
while(c<'0'||c>'9') {
if(c=='-')flag=-1;
c=getchar();
}
while(c>='0'&&c<='9') {
x=(x << 3)+ (x << 1)+(c ^ 48);
c=getchar();
}
x*=flag;
}
inline void write(int x) {
if(x<0) {
putchar('-');
x=-x;
}
if(x>9)
write(x/10);
putchar(x%10+'0');
}
int n,m,v[100],w[100],dp[30002];
int main() {
cin.tie(0);
ios::sync_with_stdio(false);
cin>>m>>n;
for(int i=1;i<=n;i++){
cin>>w[i]>>v[i];
}
for(int i=1;i<=n;i++){
for(int j=m;j>=w[i];j--){
dp[j]=max(dp[j],dp[j-w[i]]+w[i]*v[i]);//唯一不同点：价格与重要度的乘积。
}
}
cout<<dp[m];//输出
return 0;
}