算法1

(一维背包) O(n^2)

include[HTML_REMOVED]

using namespace std;
int max(int i,int j);
const int N=1010;
int v[N],w[N],dp[N];
int main(){
int n,vv;
cin>>n>>vv;
for(int i=1;i<=n;i)
cin>>v[i]>>w[i];
for(int i=1;i<=n;i)
for(int j=1;j<=vv;j++){
if(v[i]<=j)dp[j]=max(dp[j],w[i]+dp[j-v[i]]);

    }
cout<<dp[vv];

}
int max(int i,int j){
return (i>j)?i:j;
}
/
第一次写题解哈
感觉这个和普通背包差不多
一维数组写普通背包的时候我们内循环从n开始使j–，主要是因为我们i只能使用一次，如果正向的话dp[j-v[i]]就有可能包含了i使用了两次的情况
那我们这个完全背包完全可以按照这样来，因为i我们可以无限次使用，一维数组储存的就是容积为j-1时候的最优解，我们内循环直接正向从1循环到n就完事了/