一、解决问题
1、题目描述2、题目解析
动态规划：01背包问题(无物品价值)，思想相同，题目最终要求有些变化。min为最轻物品的重量，sum为所有物品总重量。假设有一个能装入容量为C(C在[min,sum]间取值)的背包和n件重量分别为w1,w2,…,wn的物品，能否从n件物品中挑选若干件恰好装满背包，要求输出不满足条件的最小容量。
该题要求数组的最小不可组成和，例如arr = {3,2,5} arr的min为2，max为10，在区间[2,10]上，4是不能被任何一个子集相加得到的值中最小的，所以4是arr的最小不可组成和；这是一个动态规划的01背包问题；根据承重和已有的重量种类阶段性计算当前承重时能够放入的重量当数组中只有2重量的时候，背包承重从2-10都可以放入2的数值 当数组中放入2和3重量的时候，背包承重从5-10 可以放入5，3-4放入3，2只能放入2 当数组中放入2，3，5重量时，背包承重10放入10，8-9放入8，7放入7，5-6 放入5…如下表：
背包
容量
2
3
4
5
6
7
8
9
10
重量2
2
2
2
2
2
2
2
2
2
重量3
2
3
3
5
5
5
5
5
5
重量5
2
3
3
5
5
7
8
8
10
最终当每个承重与放入的重量不同时，这个承重就是最小不可求和，4。
3、代码
class Solution {
public:
/**
* 正数数组中的最小不可组成和
* 输入：正数数组arr
* 返回：正数数组中的最小不可组成和
*/
int getFirstUnFormedNum(vector<int> arr, int len) {
int sum = 0, min = arr[0];
int i, j;
for (int i = 0; i < len; ++i) {
sum += arr[i];
min = arr[i] < min ? arr[i] : min;
}
vector<int> dp(sum + 1, 0);
for (i = 0; i < len; ++i) {
// 有length个数据，有length个阶段
// {2, 3, 5}
//i=0--d[10]=2 d[9]=2 d[8]=2 d[7]=2...d[2]=2
//i=1--d[10]=5 d[9]=5...d[5]=5 d[4]=3 d[3]=3
//i=2--d[10]=10 d[9]=8 d[8]=8 d[7]=7 d[6]=5 d[5]=5
for (j = sum; j >= arr[i]; --j) {
//逆序判断背包承重中能够放入的数据
//当数组中只有2的时候，背包承重从2-10都可以放入2的数值
//当数组中放入2和3的时候，背包承重从5-10可以放入5，3-4放入3，2只能放入2
//当数组中放入2，3，5时，背包承重10放入10，8-9放入8，7放入7，5-6放入5...
//dp[j-arr[i]]意思是背包承重为j时，如果已经放置了arr[i]的重量后还能放置的最大重量
if (dp[j] < dp[j - arr[i]] + arr[i]) // 对每个承重计算当前最大能放置重量
dp[j] = dp[j - arr[i]] + arr[i]; // 更新背包中能够放入的最大值
else
dp[j] = dp[j];
}
}
// 最后当承重为n时，放入的重量不为n则认为是最大不可求和
for (i = min; i <= sum; ++i) {
if (i != dp[i])
return i;
}
return sum + 1;
}
};
二、01背包问题
1、问题描述
现在有4个物品，小偷背包总容量为8，怎么可以偷得价值最多的物品？
物品编号
1
2
3
4
物品重量
2
3
4
5
物品价值
3
4
5
8
2、问题分析
记F(k,w)：当背包容量为w，现在有k件物品可以偷，所能偷到最大价值。
可以得到下表：
背包
容量
0
1
2
3
4
5
6
7
8
0
0
0
0
0
0
0
0
0
0
1: w=2, v=3
0
0
3
3
3
3
3
3
3
2: w=3, v=4
0
0
3
4
4
7
7
7
7
3: w=4, v=5
0
0
3
4
5
7
7
9
9
4: w=5, v=8
0
0
3
4
5
8
8
11
12
我们得到其状态转移方程
3、代码
int f[5][9] = { 0 };
int w[5] = { 0,2,3,4,5 };
int v[5] = { 0,3,4,5,8 };
int main()
{
int i, j;
memset(f, 0, sizeof(f));
for (i = 1; i < 5; i++)
{
for (j = 1; j < 9; j++)
{
if (w[i] > j)
f[i][j] = f[i - 1][j];
else
f[i][j] = max(f[i - 1][j], f[i - 1][j - w[i]] + v[i]);
}
for (int i = 0; i < 5; i++)
for (int j = 0; j < 9; j++)
printf("f[%d][%d]=%d\n", i, j, f[i][j]);
}
return 0;
}
