poj 3624 Charm Bracelet （0/1背包）

点击打开链接

裸0/1背包

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

const int MAXN = 15000;

int n , m;
int w[MAXN] , v[MAXN] , dp[MAXN];

int main(){
    while(scanf("%d%d" , &n , &m) != EOF){
        for(int i = 1 ; i <= n ; i++)
            scanf("%d%d" , &w[i] , &v[i]);
        int ans = 0;
        memset(dp , 0 , sizeof(dp));
        for(int i = 1 ; i <= n ; i++){
            for(int j = m ; j >= w[i] ; j--){
                dp[j] = max(dp[j] , dp[j-w[i]]+v[i]);
                ans = max(ans , dp[j]);
            }
        }
        printf("%d\n" , ans);
    }
    return 0;
}