一个人的巴黎

用户名：uq_36478041918

访问量：14988

签　名：

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

　　自我简介：

TA的其他文章

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

你可能喜欢

2004年秋浙江省计算机等级考试二级C 编程题(1) （C语言代码）

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

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

分组背包(建议先弄懂01背包或者多重背包)

　　作者: 一个人的巴黎　　　　发表时间：2022-02-17 08:38:01 浏览：455　|　评论：0　

原题链接：信息学奥赛一本通T1272-分组背包

遍历每一组的所有物品，在不超过背包容量的前提下求出最大总价值
空间优化的看不懂可以先去看[01背包](https://blog.dotcpp.com/a/83498 "01背包") 和 [多重背包](https://blog.dotcpp.com/a/84098 "多重背包")(附链接)，01背包我没有采用优化，多重背包我优化了，其实多重背包就是01背包，可以对比。
```cpp
#include<iostream>
#include<algorithm>
using namespace std;
int V,N,T;//容量，数量，组号
int w[31];//重量
int c[31];//价值
int p[11][31];//记录每组物品的是(1-n中)第几个物品
int dp[201];//装前i个物品重量为j时的最大总价值(二维优化为一维)
int main()
{
    cin>>V>>N>>T;
    for(int i=1;i<=N;i++){
        int t;
        cin>>w[i]>>c[i]>>t;//重量，价值，组号
        int len=sizeof(p[t])/sizeof(int);//计算二位数组的列数
        for(int j=1;j<=len;j++){
            if(p[t][j]==0){
                p[t][j]=i;
                break;
            }
        }
    }
    for(int i=1;i<=T;i++){ //遍历每一组
        for(int j=V;j>=0;j--){//从后往前!!!
            int len=sizeof(p[i])/sizeof(int);
            for(int k=1;k<=len;k++){//遍历每一组的所有元素
                //if(p[i][k]==0)  continue;
                if(j>=w[p[i][k]])//如果背包容量j大于等于i组下的第k个物品的重量
				//dp[j]为不选这个物品的情况
                //dp[j - w[p[i][k]]]+ c[p[i][k]]选这个物品的情况
				dp[j]=max(dp[j],dp[j-w[p[i][k]]]+c[p[i][k]]);
            }
        }
    }
    cout<<dp[V]<<endl;
    return 0;
}
```

0.0分

2 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

　　评论区

精彩推荐

WU-链表数据求和操作（C++代码）

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

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

C二级辅导-温度转换（C语言代码）

敲七（C语言代码）

班级人数（C语言代码）

分解质因数（C++代码）

JAM计数法（C语言代码）

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

1005答案错误为什么

一个人的巴黎

TA的其他文章

你可能喜欢

2004年秋浙江省计算机等级考试二级C 编程题(1) （C语言代码）

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

大神老白（C语言代码）

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

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

分组背包(建议先弄懂01背包或者多重背包)

评论区

精彩推荐

WU-链表数据求和操作（C++代码）

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

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

C二级辅导-温度转换（C语言代码）

敲七（C语言代码）

班级人数（C语言代码）

分解质因数（C++代码）

JAM计数法（C语言代码）

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

1005答案错误为什么

一个人的巴黎

TA的其他文章

你可能喜欢

2004年秋浙江省计算机等级考试二级C 编程题(1) （C语言代码）

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

大神老白 （C语言代码）

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

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

分组背包(建议先弄懂01背包 或者 多重背包)

评论区

精彩推荐

WU-链表数据求和操作 （C++代码）

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

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

C二级辅导-温度转换 （C语言代码）

敲七 （C语言代码）

班级人数 （C语言代码）

分解质因数 （C++代码）

JAM计数法 （C语言代码）

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

1005答案错误为什么

大神老白（C语言代码）

分组背包(建议先弄懂01背包或者多重背包)

　　评论区

WU-链表数据求和操作（C++代码）

C二级辅导-温度转换（C语言代码）

敲七（C语言代码）

班级人数（C语言代码）

分解质因数（C++代码）

JAM计数法（C语言代码）

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