完全背包

叔叔我啊

ACM动态规划

发布于：2021年2月12日

字数：199字

时长：1分钟

次浏览

例题

有 N 种物品和一个容量为 V 的背包，每种物品都有无限件可用。放入第 i 种物品的费用是 C[i] ，价值是 W[i] 。求解：将哪些物品装入背包，可使这些物品的耗费的费用总和不超过背包容量，且价值总和最大。

思路

按照 01 背包相同的思路，

代码

#include<cstdio>
#include<iostream>

#define maxn 1000
using namespace std;
int W[maxn], V[maxn];

int main() {
    int m, n;
    int dp[maxn];
    dp[0] = 0;
    cin >> m;
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> W[i];
        cin >> V[i];
    }
    for (int i = 1; i <= m; i++)
        for (int j = 1; j <= n; j++)
            if (i >= W[j]) {
                int choose = dp[i - W[j]] + V[j];
                if (choose > dp[i]) { dp[i] = choose; }
            }
    cout << dp[m];
    return 0;
}