01背包、完全背包模板

 1 #include<iostream>
 2 #include<cstdio>
 3 using namespace std;
 4 const int maxn=510,maxw=510;
 5 int w[maxn],v[maxw],a[maxw];
 6 int main(){
 7     int n,W;
 9     cin>>n>>W;
10     for(int i=1;i<=n;i++)
11         cin>>w[i];
12     for(int i=1;i<=n;i++)
13         cin>>v[i];    
14     for(int i=1;i<=n;i++)
15         for(int j=W;j>=w[i];j--)//j>=0
16             if(j>=w[i])  a[j]=max(a[j],a[j-w[i]]+v[i]);
17     cout<<a[W]<<endl;    
18     fclose(stdin);    
19     return 0;
20 }
输入：4 8

2 3 4 5
3 4 5 6

输出：

10

#include<bits/stdc++.h>
using namespace std;
const int maxn=510, maxw=510;
int n,W,dp[maxw],w[maxn],v[maxn];
int main(){
    cin>>n>>W;
    for(int i=1;i<=n;i++)
        cin>>w[i];
    for(int i=1;i<=n;i++)
        cin>>v[i];    
    for(int i=1;i<=n;i++)
        for(int j=w[i];j<=W;j++)//j可以从0开始，也可以从w[i]开始 
            if(j>=w[i])    dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
    cout<<dp[W];
    return 0;                
}

输入

4 10
2 3 4 7
1 3 5 9

输出

12