首页 > 其他分享 >完全背包问题

完全背包问题

时间:2023-09-05 23:11:20浏览次数:38  
标签:背包 int max 代码 完全 问题 01 include

完全背包问题

思路:

完全背包问题

f[i][j] = f[i-1][j - k*v[i]] + k * w[i]

朴素版的做法

#include<iostream>
#include<algorithm>

using namespace std;

const int N = 1010;

int n, m;
int v[N], w[N];
int f[N][N];

int main()
{
    cin>>n>>m;
    
    for(int i = 1; i<=n; i++) cin>>v[i]>>w[i]; //输入每件物品的体积和价值
    
    for(int i = 1; i<=n; i++) //前i 个物品 ,总体积不超过 j 的最大价值
        for(int j = 0; j<=m; j++)
            for(int k = 0; k*v[i] <= j; k++)
                f[i][j] = max(f[i][j], f[i-1][j-k*v[i]] + k*w[i]);
                
    cout<<f[n][m]<<endl;
    
    return 0;
}

**这个时间复杂度比较高,有的情况没办法 AC **

优化思路

我们列举一下更新次序的内部关系:

f[i, j] = max(f[i-1, j] , f[i - 1, j - v] + w , f[i-1, j - 2*v] + 2*w ,........ )
f[i,j - v] = max(          f[i-1, j - v]      ,  f[i-1, j - 2*v] + w ,......... )
由上两式,可以得出以下地推关系:
    			f[i][j] = max(f[i, j-v] + w, f[i-1][j])

有了上面的关系, 其实 k 循环可以不要了, 核心代码优化成这样

for(int i = 1; i <= n; 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][j], f[i][j - v[i]] + w[i]);
        }

这个代码和 01 背包的非优化写法很像!!!, 我们对比一下, 下面是 01 背包的核心代码

for(int i = 1 ; i <= n ; 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][j],f[i-1][j-v[i]]+w[i]);
}

两个代码其实只有一句不同(注意下标)

f[i][j] = max(f[i][j] , f[i-1][j - v[i]] + w[i]); //01背包

f[i][j] = max(f[i][j] , f[i][j - v[i]] + w[i]); //完全背包问题

因为0和1背包问题很像, 我们很容易想到进一步优化, 核心代码可以改成这样

for(int i = 1; i <= n; i++)
    for(int j = v[i]; j<=m; j++)//注意了,这里的j是从小到大枚举, 和 01 背包不一样
    {
        f[j]  = max(f[j], f[j - v[i]] +w[i]);
    }

综上所述

#include<iostream>
#include<algorithm>

using namespace std;

const int N = 1010;

int n,m;
int v[N], w[N];
int f[N];

int main()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i++) cin >> v[i] >> w[i];

    for(int i = 1; i <= n; i++)
        for(int j = v[i]; j <= m; j++)
            f[j] = max(f[j], f[j - v[i]] + w[i]);

    cout<< f[m] << endl;

    return 0;
}

标签:背包,int,max,代码,完全,问题,01,include
From: https://www.cnblogs.com/tomlove/p/17681135.html

相关文章

  • AcWing 3. 完全背包问题
    题目有$N$种物品和一个容量是$V$的背包,每种物品都有无限件可用。第i$种物品的体积是$v_i$,价值是$w_i$。求解将哪些物品装入背包,可使这些物品的总体积不超过背包容量,且总价值最大。输出最大价值。输入格式第一行两个整数,$N,V$,用空格隔开,分别表示物品种数和背包容积。......
  • 安全问题“脆弱性”日益凸显,中小企业如何选择云厂商?
    作者|曾响铃文| 响铃说“因系统升级,储值卡暂时无法使用。”2022年初,浙江某地一家连锁生活超市突然发出通知,引发居民担忧超市“关门”,纷纷要求退还储值卡内余额。实际上,这家超市的经营并没有问题,而是遭受了绵延全球数年的“比特币勒索病毒”攻击,致使记录了消费者储值数据的系统......
  • 安装php安装包时遇到问题
    提示公钥尚未安装yum-yinstallphp71wphp71w-cliphp71w-commonphp71w-develphp71w-embeddedphp71w-gdphp71w-mcryptphp71w-mbstringphp71w-pdophp71wxmlphp71w-fpmphp71w-mysqlndphp71w-opcachephp71w-pecl-memcachedphp71wpecl-redisphp71w-pecl-mongodb ......
  • 1 C++基础问题总结
    C++基础1C和C++有什么区别?C++是面向对象,C面向过程C++引入new/delete运算符,取代了C中的malloc/free库函数;C++有引用的概念,C没有C++有类的概念,C没有C++有函数重载,C没有2a和&a有什么区别?比如inta[10];int(*p)[10]=&aa是数组名,是数组首元素地址,+1表示地址值加上一......
  • 关于移动端开发和web开发轮转图滑动问题
    当web端切换到移动端时,发现页面slider不能够正常去滑动轮转图,原因是,在开发时,如果在打开页面是web页面状态,然后去切换到移动端时候,没有监听到移动端的时间,比如touchmove事件,click事件等等。解决的方法是刷新一下页面就好。   ......
  • 【坑】VUE中动态数据使用 wow.js 没效果的问题
    一般来说正常使用都是在mounted函数中mounted(){this.$nextTick(()=>{this.$wow.init()})}这样如果是死数据是可以正常出现效果的但是如果是请求回来的数据是没有效果的需要改一下生成时机  此处的newList即为请求的数据watch:{newsl......
  • Java语言与其环境:常见问题解答
    Java语言与其环境:常见问题解答在本博客文章中,将深入探讨Java编程语言的特点和环境,解释一些常见的关于Java的疑问。Java语言的特点是什么?Java是一种高级编程语言,它具有以下几个主要的特点:简单:Java的语法与C和C++非常相似,但它消除了这两种语言中的许多复杂和很少使用的特性,如......
  • 项目相关的问题记录
    1.你们的服务部署在多少台机器上面?集群部署,至少两台,2核4G,一台如果挂掉了可以容灾的切换。2.RocketMq设置了多少消费者?如何保证高可用的问题。一个集群可以有多个消费者。是3个消费者,可以设置上下线。 默认情况下就是集群消费,这种模式下⼀一个消费者组共同消费⼀一个主题的......
  • 【css兼容】flex在低版本 chrome 浏览器的兼容问题
    https://blog.csdn.net/weixin_43841308/article/details/111246537 前言【感官】使用ElementUI构建如下布局【逻辑】具体代码:【现象】谷歌浏览器44.0.2403.125m版本显示main内容不全谷歌浏览器57.0.2987.133版本页面正常flex兼容性【猜想】display:flex在网站兼容性......
  • 多线程中的不同区域的变量的安全性问题测试
    如果是方法中的变量,不存在线程安全问题。方法中的变量代码片段:publicclassHasSelfPrivateNum{publicvoidaddI(StringuserName){ //这里的num变量是存在于addI这个方法里面的intnum=0;try{if(userName.equals("a")){......