AcWing 4. 多包 I(一看就会,懒人专用)+saber精简代码

历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

AcWing 4. 多包 I(一看就会,懒人专用)+saber精简代码原题链接简单

作者：

9年级的蒟蒻 , 2020-06-07 23:09:41 , 所有人可见 , 阅读 36927

405

64

2022.10.16 14:00左右破百赞

2023.7.5 14:00左右破二百赞

2022.11.16 22:09 写出多包II的题解链接

~~请大家点个赞~~，有写的不好的可以在评论区评论

题目描述

有 $N$ 种物品和一个容量是 $V$ 的背包。

第 $i$ 种物品最多有 $s_{i}$ 件，每件体积是 $v_{i}$，价值是 $w_{i}$。

求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。
输出最大价值。

输入格式
第一行两个整数，$N$，$V$，用空格隔开，分别表示物品种数和背包容积。

接下来有 $N$ 行，每行三个整数 $v_{i},w_{i},s_{i}$，用空格隔开，分别表示第 $i$ 种物品的体积、价值和数量。

输出格式
输出一个整数，表示最大价值。

数据范围
$0<N,V≤100$
$0<v_{i},w_{i},s_{i}≤100$

样例

输入样例
4 5
1 2 3
2 4 1
3 4 3
4 5 2
输出样例：
10

分析

当 $s_{i} = 1$ 时，相当于01背包中的一件物品
当 $s_{i} > 1$ 时，相当于01背包中的多个一件物品
故我们可以死拆(把多重背包拆成01背包)

别忘了点赞

C++ 代码

#include <bits/stdc++.h>
using namespace std;
int a[10005],b[10005],t=0,n,m,dp[10005]={ },w,v,s;
int main()
{
    cin>>n>>m;
    while(n--)
    {
        cin>>v>>w>>s;
        while(s--)
        {
            a[++t]=v;
            b[t]=w;
        }//死拆，把多重背包拆成01背包
    }
    for(int i=1;i<=t;i++)
    for(int j=m;j>=a[i];j--)
    dp[j]=max(dp[j-a[i]]+b[i],dp[j]);//直接套01背包的板子
    cout<<dp[m]<<endl;
    return 0;
}

update:2022.10.16 18:06 优化，稍微短了一点(把for改成while)（

saber简化代码

#include <bits/stdc++.h>
using namespace std;
int dp[1005],n,t,v,w,s;
main()
{
    cin>>n>>t;
    while(n--)
    {
    cin>>w>>v>>s;
    while(s--)
    for(int j=t;j>=w;j--)
    dp[j]=max(dp[j],dp[j-w]+v);
    }
    cout<<dp[t];
}

79 评论

mouse-knight 2022-02-22 18:29

其实那个死拆还有后面的01背包不用分开吧？当成s个物品做就可以了。

#include <bits/stdc++.h>
using namespace std;
int a[10005],b[10005],t=0,n,m,dp[10005]={ },w,v,s;
int main()
{
    cin>>n>>m;
    while(n--){
        cin>>v>>w>>s;
        while(s--){
            for(int j=m;j>=v;j--)
                dp[j]=max(dp[j-v]+w,dp[j]);//直接套01背包的板子
        }
    }
    cout<<dp[m]<<endl;
    return 0;
}

9年级的蒟蒻 2022-02-22 18:44

分开的话能更好的理解

mouse-knight 2022-02-24 19:57 回复了 9年级的蒟蒻的评论

jeffstart 2022-07-04 12:14 回复了 mouse-knight 的评论

good

comi.Z 2023-03-09 21:07

老哥代码真好，但是没看懂，还能具体一点吗

mouse-knight 2023-09-29 23:43 回复了 comi.Z 的评论

就是有s个就做s次01背包嘛

hema5177 2022-10-18 21:25

《9年级的神犇》

dp亿生之敌 2022-07-29 09:05

好贴心还为saber玩家考虑了必须点赞啊

Miracle_05 2023-09-24 19:34

啥是saber哇

两只的橘猫 11个月前回复了 Miracle_05 的评论

打挑战的，需要代码少这样写起来快

Learningmania 2023-05-31 09:55

我非常想说这种想法非常适合我这种不太懂的变通的娃,orz

好喝不过冰阔乐 2022-11-08 21:38

$好耶好耶 (＾－＾)V $

Love_cheng 2022-09-13 16:51

爆赞

acwing_4785 9个月前

#include <bits/stdc++.h>
using namespace std;
const int maxn = 120;
int dp[maxn] , v[maxn] , w[maxn] , s[maxn];
int N ,V;
int main(){
    scanf("%d%d" , &N , &V); 
    for(int i = 0; i < N ;i ++)
        scanf("%d%d%d" , v + i , w + i , s + i);
    memset(dp , 0 , sizeof(dp));
    for(int i = 0 ;i  < N ; i ++) 
        for(int k = 0 ; k < s[i] ; k ++)
            for(int j = V ; j >= v[i] ; j --)
                dp[j] = max(dp[j] , dp[j - v[i]] + w[i]);
    printf("%d" , dp[V]);
    return 0;
}

用三重循环也可以

迷你世界花小楼 2023-11-20 12:35

看到死拆就笑了，大哥牛皮

一只CPC 2023-05-26 21:38

泰裤辣

摇曳 2022-10-25 21:03

Yuan_2 2022-10-23 21:18

wc太diao了

无敌的拖拉机 2个月前

好喜欢这种符合猪脑子体制的代码 dei佬Orz

上善若水_62 2个月前

可以2进制拆分

林禾雨 7个月前

第一次在acwing上点赞，写的好！

狂生 7个月前

#include<iostream>
using namespace std;

const int N = 10010;
int f[N][N];
int v[N], w[N];
int n, m;

int main()
{
    cin>>n>>m;

    int t = 1;
    while(n--)
    {
        int a, b, c;
        cin>>a>>b>>c;
        while(c--)
        {   
            v[t] = a;
            w[t++] = b;
        }
    }
    //cout<<w[7];
    for(int i = 1; i<=t-1;i++)
    {
        for(int j = 0; j<=m; j++)
        {
            f[i][j] = f[i-1][j];
            if(j-v[i]>=0)
            f[i][j] = max(f[i-1][j], f[i-1][j-v[i]]+w[i]);
        }
    }
    cout<<f[t-1][m];
}

这个是二维的，差一个数据，不过应该容易理解

睡在树上的鱼 11个月前

%%%%%

lzx19 2023-10-09 14:56

%%%

Miracle_05 2023-09-24 19:35

啥是saber，有无大佬解释一下

两只的橘猫 11个月前

打挑战的，需要代码少这样写起来快

li2022 2023-08-26 11:33

想问一下，当前容量不够时，f[i][j]=f[i-1][j]这行代码体现在哪里？

acwing_13295 2023-10-30 18:31

体现在for循环max里面，01背包是从满容量开始到v[i]进行循环，dp数组默认全部是0 ，也就是说当第一个n-v[i]出现的时候状态方程才更新，也就是放物品

hu8 2023-07-16 18:25

#include <iostream>
#define N 15000
using namespace std;
int n,m;
int cnt;
int w[N],v[N];
int f[N];
//硬拆  用数组一个个的存起来，体积价值一样没有关系我从1开始往后存，之后再用01 的板子
int main()
{
    cin>>n>>m;
    while(n--)
    {
        int x,y,z;
        cin>>x>>y>>z;
        while(z--)
        {
            v[++cnt]=x;
            w[cnt]=y;
        }
    }
    for(int i=1;i<=cnt;i++)
    {
        for(int j=m;j>=v[i];j--)
        {
            f[j]=max(f[j],f[j-v[i]]+w[i]);
        }
    }
    cout<<f[m]<<endl;
    return 0;
}