Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Study dynamic programming - back pack problem - Feb. 14, 2018
/*
01背包问题
背包九讲:http://www.cnblogs.com/jbelial/articles/2116074.html
其状态转移方程便是:f[i][v] = max{f[i-1][v], f[i-1][v-c[i]] + w[i]}。
这个方程非常重要,基本上所有跟背包相关的问题的方程都是由它衍生出来的。
**详细解释**
“将前 i 件物品放入容量为 v 的背包中” 这个子问题,若只考虑第 i 件物品的策略(放或不放),那么就
可以转化为一个只牵扯前 i-1 件物品的问题。如果不放第 i 件物品,那么问题就转化为“前 i-1 件物品放入
容量为 v 的背包中”;如果放第 i 件物品,那么问题就转化为“前 i - 1 件物品放入剩下的容量为 v - c[i]的背包中”,
此时能获得的最大价值就是 f [i - 1][v - c[i]]再加上通过放入第 i 件物品获得的价值 w[i]。
*/
int main()
{
//int m = 120;
//int n = 5;
//vector<int> w = { 0, 40, 50, 70, 40, 20 };
//vector<int> v = { 0, 10, 25, 40, 20, 10 };
int m, n; //m重量,n数量
while (cin >> m >> n)
{
vector<int> w(n + 1, 0);
vector<int> v(n + 1, 0);
for (int i = 1; i <= n; i++)
{
int tmp;
cin >> tmp;
w[i] = tmp;
}
for (int i = 1; i <= n; i++)
{
int tmp;
cin >> tmp;
v[i] = tmp;
}
vector< vector<int> > vec(n + 1, vector<int>(m + 1, 0));
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
{
if (w[i] > j)
vec[i][j] = vec[i - 1][j];
else
{
int tmp1 = v[i] + vec[i - 1][j - w[i]];
int tmp2 = vec[i - 1][j];
vec[i][j] = tmp1 > tmp2 ? tmp1 : tmp2;
}
}
}
double val = vec[n][m] * 0.1;
cout << val << endl;
}
system("pause");
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment