shuaspeedl

用户名：971973918

访问量：656

签　名：

除了长得帅没有什么优点

等　　级
排　　名	26479
经　　验	520
参赛次数	0
文章发表	2
年　　龄	0
在职情况	学生
学　　校	辽宁工程技术大学
专　　业	软件工程

　　自我简介：

TA的其他文章

weihaoyang.数组与字符串的转换
浏览：188

你可能喜欢

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

C语言训练-求s=a+aa+aaa+aaaa+aa...a的值（C++代码）（手动优化一下计算）

weihaoyang. 背包问题

　　作者: shuaspeedl　　　　发表时间：2020-02-15 15:54:27 浏览：171　|　评论：0　

### 听背包九讲做一些摘要:
对于01背包问题：
假如一开始对于dp[][]数组全部赋值为0（即可以定义为全局变量）
dp[n][m]就是最优解，，不需要进行dp[n][0]~dp[n][m]进行枚举;

### 倘若要求的是容量恰好为m时的最优解：(背包容量特定的最优解问题)
应该 int dp[0]=0;
		dp[i]=-INF//其余i值赋值为负无穷
(就不用数学公式推导了)

# 01背包
    for(int i=1;i<=n;i++)
    {
        for(int j=v;j>=weight[i];j--)
        {
            dp[j]=max(dp[j],dp[i-weight[i]]+value[i]);
        }
    }
	
# 完全背包
    for(i=1;i<=n;i++)
    {
        for(j=weight[i];j<=v;j++)
        {		
              dp[j]=max(dp[j],dp[j-weight[i]]+value[i]);	
        }
    }
# 多重背包
多重背包由于物品的数量也是有限制的，所以和01背包也是有相似之处的。
贴一下算法部分：
    for(int i=1;i<=n;i++)
    { 
        for(int j=v;j>=0;j--)
        { for(int k=1;k<=s&&k*v[i]<=j;k++)//s 是该物品的数量
            dp[j]=max(dp[j],dp[i-k*weight[i]]+k*value[i]);
        }
    }
ps:该解法时间复杂度O(N3) 有点大，测试数据大一点的话很容易tle的 233333
# 多重背包 II
上边用三重循环做多重背包的话很容易tle，这里记录一下学习到的二进制法来优化一下时间复杂度。
### 二进制法主要思路是将多重背包分解成s个零一背包来求解
贴一下代玛~:(只写了主要部分)

struct good{
int v;
int w};
vector<good> goods;
cin>>n>>m;
for(int i=0;i<n;i++)
{
int v , w ,s;
cin>>v>>w>>s;        // v 是物品的价值，w是重量，s是该某一个物品的个数
for(int k=1;k<=s;k*=2){
s-=k;
goods.push_back({v*k,w*k});
} if(s>0) goods.push_back({s*v,s*w});
}
for(auto good:goods)
for(int j=m;j>=good.v;j++){
f[j]=max(f[j-1],f[j-good.w]+good.v);
}
cout<<f[m]<<endl;
## 完全背包和01背包区别在于第二个for循环是从小到大还是从大到小，
01背包从大到小是因为01背包每件物品只有选和不选两种状态，所以采取从大到小

然而完全背包，每件物品可以被选无数次，所以可以从小到大枚举。
完全背包也可以采取二位数组来进行动态规划，再加第三层循环来控制物品的个数k，但是有可能tle

0.0分

3 人评分

C语言网推出会员服务，提供C/C++/算法/Python等多套视频学练课程+源码资源社群答疑+私活推荐等资源，享受丰富的技术学习到变现的乐趣，以含金量和学习效果勇敢挑战同类辅导！点击了解开通

shuaspeedl

TA的其他文章

你可能喜欢

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

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

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

【蟠桃记】（C语言代码）

C语言训练-求s=a+aa+aaa+aaaa+aa...a的值（C++代码）（手动优化一下计算）

weihaoyang. 背包问题

评论区

精彩推荐

大神老白（C语言代码）

【回文数(二)】（C语言代码）

字符串对比（C语言代码）

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

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

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

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

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

A+B for Input-Output Practice (III) （C语言代码）

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

shuaspeedl

TA的其他文章

你可能喜欢

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

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

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

【蟠桃记】 （C语言代码）

C语言训练-求s=a+aa+aaa+aaaa+aa...a的值 （C++代码）（手动优化一下计算）

weihaoyang. 背包问题

评论区

精彩推荐

大神老白 （C语言代码）

【回文数(二)】 （C语言代码）

字符串对比 （C语言代码）

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

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

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

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

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

A+B for Input-Output Practice (III) （C语言代码）

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

【蟠桃记】（C语言代码）

C语言训练-求s=a+aa+aaa+aaaa+aa...a的值（C++代码）（手动优化一下计算）

　　评论区

大神老白（C语言代码）

【回文数(二)】（C语言代码）

字符串对比（C语言代码）