一个人的巴黎

用户名：uq_36478041918

访问量：15101

签　名：

等　　级
排　　名	105
经　　验	8320
参赛次数	1
文章发表	70
年　　龄	0
在职情况	学生
学　　校	NTU
专　　业	计算机科学与技术

　　自我简介：

TA的其他文章

数据结构-二叉排序树的基本操作【C++】
浏览：85

你可能喜欢

完全背包问题(动态规划时间优化空间优化)

　　作者: 一个人的巴黎　　　　发表时间：2022-02-16 18:05:17 浏览：164　|　评论：0　

原题链接：信息学奥赛一本通T1268-完全背包问题

确定状态
1. 对于每个总重量，我们能知道对应的最大价值是多少，就能求出答案
2. 最后一步：第n种物品(重量W[n]，价值C[n])是否进入背包
情况一：如果前n-1种物品能拼出W，最大价值是C，前n个物品也能拼出W并且总价值是C
情况二：如果当前n-1种物品能拼出W-W[n]，最大总价值C，则再加上最后的物品（重量W[n]，价值C[n]），拼出W，总价值C+C[n]
3. 情况一和情况二的最大值=用n种物品拼出重量W时的最大总价值

转移方程
状态：设dp[i][j]=用前i种物品有拼出重量j时最大总价值(数量不限)
dp[i][j]=max{dp[i-1][j], dp[i-1][j-W[i]]+C[i], dp[i-1][j-2W[i]+2C[i]], ...}

|   |  0 | 1  | 2  | 3  | 4  | 5  | 6  | ...  | m  |
| ------------ | ------------ | ------------ | ------------ | ------------ | ------------ | ------------ | ------------ | ------------ | ------------ |
| dp[i-1]  |   |   |   |   |   |   |   |   |   |
| dp[i]  |   |   |   |   |   |   |   |   |   |
假设W[i]=2(i物品重量为2),C[i]=c
dp[i][4]=max(dp[i-1][4],dp[i-1][2]+c,dp[i-1][0]+c)
dp[i][6]=max(dp[i-1][6],dp[i-1][4]+c,dp[i-1][2]+2c,dp[i-1][0]+3c)
当我们计算dp[i][6]时，dp[i-1][4]+c,dp[i-1][2]+2c,dp[i-1][0]+3c的最大值已经确认了，就存在dp[i][4]+c中，就无需重复确认。
因此dp[i][j]=max(dp[i-1][j],dp[i][j-W[i]]+C[i])

```cpp
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
int n,m;//背包容量m，物品数量n
int w[31];//物品重量
int c[31];//物品价值
int dp[31][201];//dp[i][j]:表示装入前i种物品重量为j时的最大总价值
int main()
{
    cin>>m>>n;
    for(int i=1;i<=n;i++)
        cin>>w[i]>>c[i];
    memset(dp,0,sizeof(dp));
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            dp[i][j] = dp[i - 1][j];//装不下
            if(j>=w[i])//装的下
                dp[i][j]=max(dp[i-1][j],dp[i][j-w[i]]+c[i]);
        }
    }
    cout<<"max="<<dp[n][m]<<endl;
    return 0;
}
```

空间优化如下：

![](/image_editor_upload/20220216055545_69165.png)
我们发现 dp[i][j]=max(dp[i-1][j],dp[i][j-w[i]]+c[i]);
dp[i][j]的值来源于上一行的旧值和本行前面的某个新值，因此我们可以直接覆盖旧值
dp[j]=max(dp[j],dp[j-w[i]]+v[i])
但是顺序要从左往右，这样才能不断用到新值，即从前往后刷新

```cpp
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
int n,m;//背包容量m，物品数量n
int w[31];//物品重量
int c[31];//物品价值
int dp[201];//dp[i][j]:表示装入前i种物品重量为j时的最大总价值
int main()
{
    cin>>m>>n;
    for(int i=1;i<=n;i++)
        cin>>w[i]>>c[i];
    memset(dp,0,sizeof(dp));
    for(int i=1;i<=n;i++){
        for(int j=0;j<=m;j++){//important!!!
            if(j>=w[i])
                dp[j]=max(dp[j],dp[j-w[i]]+c[i]);
        }
    }
    cout<<"max="<<dp[m]<<endl;
    return 0;
}
```

0.0分

1 人评分

新上线《蓝桥杯辅导》课程，近五年的蓝桥杯省赛与国赛真题都有，从读题开始理解题意、梳理思路、实现代码再提交评测全过程，可有效提升获奖比例甚至进国赛！课程介绍、试听请猛击这里

一个人的巴黎

TA的其他文章

你可能喜欢

C二级辅导-求偶数和（C++代码）

求最大公约数-模板题

人民币问题（C语言代码）

母牛的故事（C语言代码）

数列（C++代码）

完全背包问题(动态规划时间优化空间优化)

评论区

精彩推荐

字符串的输入输出处理（C语言代码）

简单的a+b （C语言代码）

C语言程序设计教程（第三版）课后习题6.5 （C++代码）

矩阵乘方（C语言代码）

C语言程序设计教程（第三版）课后习题11.1 （C语言代码）

C二级辅导-等差数列（C语言代码）

字符逆序（C语言代码）

小O的乘积（C语言代码）

C语言程序设计教程（第三版）课后习题9.2 （C语言代码）

C语言程序设计教程（第三版）课后习题10.7 （C++代码）

一个人的巴黎

TA的其他文章

你可能喜欢

C二级辅导-求偶数和 （C++代码）

求最大公约数-模板题

人民币问题 （C语言代码）

母牛的故事 （C语言代码）

数列 （C++代码）

完全背包问题(动态规划 时间优化 空间优化)

评论区

精彩推荐

字符串的输入输出处理 （C语言代码）

简单的a+b （C语言代码）

C语言程序设计教程（第三版）课后习题6.5 （C++代码）

矩阵乘方 （C语言代码）

C语言程序设计教程（第三版）课后习题11.1 （C语言代码）

C二级辅导-等差数列 （C语言代码）

字符逆序 （C语言代码）

小O的乘积 （C语言代码）

C语言程序设计教程（第三版）课后习题9.2 （C语言代码）

C语言程序设计教程（第三版）课后习题10.7 （C++代码）

C二级辅导-求偶数和（C++代码）

人民币问题（C语言代码）

母牛的故事（C语言代码）

数列（C++代码）

完全背包问题(动态规划时间优化空间优化)

　　评论区

字符串的输入输出处理（C语言代码）

矩阵乘方（C语言代码）

C二级辅导-等差数列（C语言代码）

字符逆序（C语言代码）

小O的乘积（C语言代码）