大疆创新 2020校招 软件类岗位A卷 应该吃哪个呢（多重有限背包问题）

      这道题是一个多重背包问题，将其转化为01背包后既可以解出。

#include 
#include
#define INF (0x3f3f3f3f)using namespace std;int Price[2001], Manyi[2001];		//100*20
int Data[2001][10001];int main()
{int N, T;while (cin >> N >> T)		//代表有输入{memset(Price, 0, sizeof(Price));memset(Manyi, 0, sizeof(Manyi));int count = 1;for (int i = 0; i < N; i++){int price, manyi, number;int j = 0;cin >> price >> manyi >> number;while (number >= pow(2, j))		//将多重背包转化为01背包{Price[count] = pow(2, j) * price;Manyi[count] = pow(2, j) *manyi;number -= pow(2, j);count++;j++;}for (; j >= 0; j--){if (number >= pow(2, j)){Price[count] = pow(2, j) * price;Manyi[count] = pow(2, j) *manyi;number -= pow(2, j);count++;}//else if (number == 0)//	break;}//cout << count << endl;}for (int i = 1; i <= count; i++){for (int j = 1; j <= T; j++){if (j >= Price[i])Data[i][j] = max(Data[i - 1][j], Data[i - 1][j - Price[i]] + Manyi[i]);elseData[i][j] = Data[i - 1][j];}}cout << Data[count][T] << endl;}/*Solution SO;SO.longestDecomposition(a);*/return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！