11013: 【原1013】无限背包

题目

题目描述

author: 韩立 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1013

Description

你现在有一个体积为V的大袋子，有N种物品，假设每种物品的数量有无限多个，而且第i种物品的体积是c[i],价值是w[i],请选择一些物品放入袋中，使袋中物品的价值总和最大。

注意每种物品的数量是无限多的；对于放入袋中的同种物品数量没有限制。

Input Format

第一行包含两个正整数V和N，分别代表袋子的体积和物品的种类数。

以下N行分别由2个正整数组成，代表每种物品的体积和价值。

\(V \leq 10000, N \leq 1000\)。

保证操作可在C++ int范围内完成。

Output Format

输出一个整数，表示最大的价值总和

Sample Input

5 3
2 3
3 2
4 1

Sample Output

6

FineArtz's solution

#include <iostream>
#include <map>
using namespace std;

int main(){
    map<int, int> bucket;
    int f[10005] = {0};
    int v, n;
    cin >> v >> n;
    while (n--){
        int vi, wi;
        cin >> vi >> wi;
        if (bucket.find(vi) != bucket.end()){
            if (bucket[vi] < wi) bucket[vi] = wi;
        }
        else bucket[vi] = wi;
    }
    for (auto i = bucket.begin(); i != bucket.end(); ++i)
        for (int j = i->first; j <= v; ++j)
            f[j] = max(f[j], f[j - i->first] + i->second);
    cout << f[v] << endl;
    return 0;
}

ligongzzz's solution

#include "iostream"
using namespace std;
int weight[1009] = { 0 }, value[1009] = { 0 },dp_data[10009] = { 0 };
int dp(int v, int n) {
    if (dp_data[v] > 0) return dp_data[v];
    int ans = 0;
    for (int i = 0; i < n; ++i) 
        if (weight[i] <= v) {
            auto temp = dp(v - weight[i], n) + value[i];
            ans = temp > ans ? temp : ans;
        }
    dp_data[v] = ans;
    return ans;
}
int main() {
    int v, n;
    cin >> v >> n;
    for (int i = 0; i < n; ++i)
        cin >> weight[i] >> value[i];
    cout << dp(v, n);
    return 0;
}

yyong119's solution

#include <iostream>
int w[1001],v[1001],f[10001];
int n,m,i,j,k;
int main(){
    using namespace std;
    cin>>m>>n;
    for (i=1; i<=n; i++) cin>>w[i]>>v[i];
    for (i=1; i<=m; i++)
        for (j=1; j<=n; j++)
            if ((i-w[j]>=0)&&(f[i]<f[i-w[j]]+v[j])) f[i]=f[i-w[j]]+v[j];
    cout<<f[m];
    return 0;
}