目录

一、背包简介

二、背包种类

1.01背包

1.二维

2.一维

2.完全背包

问题描述

三、例题

1.金明的预算方案

2.机器分配

一、背包简介

背包其实就是动态规划，可以推出方程，但因为其比较常见，所以单独挑出来。

二、背包种类

1.01背包

因为他只有选和不选两种，所以被比作01；

1.二维

问题描述：

给定 n 件物品，物品的重量为 weight，对应的价值为 value。现挑选物品放入背包中，假定背包能承受的最大重量 W 为 m，问应该如何选择装入背包中的物品，使得装入背包中物品的总价值最大？

令 dp[i][w] 表示前 i 件物品放入容量为 w 的背包中可获得的最大价值。为了方便处理，我们约定下标从 1 开始。

对于编号为 i 的物品：

• 如果选择它，那么，当前背包的最大价值等于” i 号物品的价值“ 加上 ”减去 i 号物品占用的空间后剩余的背包空间所能存放的最大价值“，即dp[i][k] = value[i] + dp[i-1][k-weight[i]]；
• 如果不选择它，那么，当前背包的价值就等于前 i-1 个物品存放在背包中的最大价值，即 dp[i][k] = dp[i-1][k]

转移方程：

dp(i,j) = max(dp(i-1,j),dp(i-1,j-w(i))+v(i));

代码实现如下：

#include "iostream"
#include "iomanip"
using namespace std;

//最优解状态空间
int dp[100][100];
int value[100];
int weight[100];
int n,m;
int main(){
	cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>weight[i]>>value[i];

    //递推求解dp状态
    for (int i = 1; i <=n ; ++i) {//3个物品
        for (int j = 1; j <=m ; ++j) {//背包空间
            //不选i物品，最大与dp[i-1][j]相等
            int without = dp[i-1][j];
            //选i物品：
            // 首先必须空间能放得下i物品
            // 其次选择该物品的价值：当前物品的价值 + 剩余空间的最大价值
            int with = weight[i]<=j?dp[i-1][j-weight[i]]+value[i]:0;
            dp[i][j] = max(without,with);
        }
    }

    //打印dp状态
    for (int i = 1; i <=n ; ++i) {
        for (int j = 1; j <=m ; ++j) {
            cout<<setw(m)<<dp[i][j]<<"  ";
        }
        cout<<endl;
    }

}

2.一维

我们之前分析出01背包的状态转移方程：

dp[i][k] = max(value[i] + dp[i-1][k-weight[i]], dp[i-1][k])

观察上面的代码，会发现，当更新dp[i][k]时，只与dp[i-1][..]有关，也就是说，我们没有必要使用O(n*W)的空间，而是只使用O(W)的空间即可。

for (int i = 1; i <=n ; ++i) {
        for (int k = c; k >=1 ; k--) {
            //选
            int value_with = (k - weight[i] >= 0) ? (dp[k - weight[i]] + value[i]) : 0;
            //不选
            int value_without = dp[k];

            dp[k] = max(value_with,value_without);
        }
    }

这里的状态转移方程变成了：

dp[k] = max(value[i]+dp[k-weight[i]], dp[k])

2.完全背包

问题描述

有n种物品，每种物品的单件重量为w[i]，价值为c[i]。现有一个容量为V的背包，问如何选取物品放入背包，使得背包内物品的总价值最大。其中每种物品都有无穷件。

对于01背包问题，每种物品只有两种选择：选和不选，我们推导的转移方程如下：

dp[k] = max(value[i]+dp[k-weight[i]], dp[k])

完全背包问题中，每个物品有无限件，也就是从每种物品的角度考虑，与它相关的策略并非选或者不选两种。而是：选0件、选1件、选2件…等等多种策略。

我们借鉴01背包问题的思路，将每种选择策略的结果都计算出来，然后取所有策略状态的最大值，转移方程如下：

令dp[i][j]表示前i种物品放入容量为j的背包的最大价值：

dp[i][j] = max{dp[i-1][j-k*weight[i]]+k*value[i]|0<=k*value[i]<=j}

核心代码：

//完全背包：递推求解dp状态
    for (int i = 1; i <=n ; ++i) {//物品
        for (int j = 1; j <=c ; ++j) {//背包空间
            //这里需要计算所有策略，对应01背包问题，这里只需要计算选和不选两种策略
            for (int k = 0; k*weight[i] <= j ; ++k) {
                dp[i][j] = max(dp[i][j],dp[i-1][j-k*weight[i]]+k*value[i]);
            }
        }
    }

三、例题

1.金明的预算方案

详情：金明的预算方案_维克托的博客-CSDN博客

由题目我们知道，一个主件最多有两个附件，且必须先买主件，所以：

1.只选主件，不选附件：dp[j]=max(dp[j],dp[j-w[i]]+v[i]);

2.选主件和第一个附件：dp[j]=max(dp[j],dp[j-w[i]-w1[i][1]]+v[i]+v1[i][1]);

3.选主件和第二个附件：dp[j]=max(dp[j],dp[j-w[i]-w1[i][2]]+v[i]+v1[i][2]);

4.选主件和所有附件：dp[j]=max(dp[j],dp[j-w[i]-w1[i][1]-w1[i][2]]+v[i]+v1[i][1]+v1[i][2]);

2.机器分配

总公司拥有高效设备M台，准备分给下属的N个分公司。各分公司若获得这些设备，可以为国家提供一定的盈利。
问：如何分配这M台设备才能使国家得到的盈利最大？求出最大盈利值。其中M≤15，N≤10。

分配原则：每个公司有权获得任意数目的设备，但总台数不超过设备数M。

输入格式:

输入包含一组数据：第一行有两个数，第一个数是分公司数N，第二个数是设备台数M。

接下来是一个N*M的矩阵，表明了第 I个公司分配 J台机器的盈利。

输出格式:

输出第一行为最大盈利值；

接下来有n行，分别为各分公司分配的机器数。

限制:

空间限制：128MByte

时间限制：1秒

样例:

输入： 3 3

30 40 50

20 30 50

20 25 30
输出：

70

1 1

2 1

3 1

提示:

要求答案的字典序最小

#include<iostream>
using namespace std;
int n,dp[20][20],m,v[20][20],sum[20][20];
void print(int i,int j){
	if(i==0) return;
	print(i-1,j-sum[i][j]);
	cout<<i<<" "<<sum[i][j]<<endl;
}
int main() {
	cin>>n>>m;
	for(int i=1; i<=n; i++)
		for(int j=1; j<=m; j++)
			cin>>v[i][j];
	for(int i=1; i<=n; i++)
		for(int j=1; j<=m; j++) 
			for(int k=0; k<=j; k++) 
				if(j>=k)
					if(dp[i][j]<dp[i-1][j-k]+v[i][k]) {
						dp[i][j]=dp[i-1][j-k]+v[i][k];
						sum[i][j]=k;
					}
	cout<<dp[n][m]<<endl;
	print(n,m);
	return 0;
}