完全背包问题

共计 599 个字符，预计需要花费 2 分钟才能阅读完成。

题目

设有 n 种物品，每种物品有一个重量及一个价值。但每种物品的数量是无限的，同时有一个背包，最大载重量为 M，今从 n 种物品中选择若干件（同一种物品可以多次选取），使其重量的和小于等于 M，而价值的和最大。

输入描述

第一行：两个整数，M（背包载重，M\le200）和 N（物品数量，N\le30）。

第 2\sim (N+1) 行：每行两个整数 W_i, C_i，表示每个物品的重量和价值。

输出描述

仅一行，max= 一个数，表示最大总价值。

样例

输入

10 4
2 1
7 9
1 1
4 5

输出

max=12

答案

#pragma GCC optimize(3)
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

int main(){ios::sync_with_stdio(false);
    cin.tie(0);

    int m, n; cin >> m >> n;
    int *b = new int[m+1];
    memset(b, 0, sizeof(b));
    while(n--){
        int w, c; cin >> w >> c;
        for(int i=w; i<=m; i++){if(w<=i) b[i] = max(b[i], b[i-w]+c);
        }
    }
    cout << "max=" << *max_element(b, b+m+1);
    return 0;
} 

解析

简单的递推，可以自己画一张表就懂了。