- #include"iostream"
- using namespace std;
- int main()
- {
- int item_num = 5;
- int bag_weight = 10;
- int bag_volume = 10;
- int each_weight[5] = {
- 2, 2, 6, 5, 4
- };
- int each_volume[5] = {
- 2, 2, 6, 5, 4
- };
- int each_value[5] = {
- 6, 3, 5, 4, 6
- };
- //记录表
- int record[item_num][bag_weight+1][bag_volume+1];
- //第n个物品的情况 ,填最后一行
- for(int j=0; j<bag_weight+1; j++)
- {
- for(int k=0; k<bag_volume+1; k++)
- {
- if(each_weight[4] <= j && each_volume[4] <=k)
- {
- record[4][j][k] = each_value[4];
- }
- else
- {
- record[4][j][k] = 0;
- }
- }
- }
- //往上填上面行
- for(int i= item_num-2; i>=0; i--)
- {
- for(int j=0; j<bag_weight+1; j++)
- {
- for(int k=0; k<bag_volume+1; k++)
- {
- if(each_weight[i] <= j && each_volume[i] <= k) // m[i][j]=max(m[i+1][j], m[i+1][j-w[i]]+v[i]);
- {
- if(record[i+1][j][k] < (record[i+1][j-each_weight[i]][k-each_volume[i]] + each_value[i]))
- {
- record[i][j][k] = (record[i+1][j-each_weight[i]][k-each_volume[i]] + each_value[i]);
- }
- else
- {
- record[i][j][k] = record[i+1][j][k];
- }
- }
- else
- {
- record[i][j][k] = record[i+1][j][k];
- }
- }
- }
- }
- /*
- for(int i=0; i<5; i++)
- {
- cout << i+1 << " ";
- for(int j=0; j<11; j++ )
- {
- for(int k=0; k<11; k++)
- {
- cout << record[i][j][k] << " ";
- }
- cout << endl;
- }
- cout << endl;
- }*/
- for(int k=0; k<bag_volume+1; k++)
- {
- cout << " % 0 1 2 3 4 5 6 7 8 9 10" << endl;
- for(int i=0; i<5; i++)
- {
- cout << i+1 << " ";
- for(int j=0; j<11; j++ )
- {
- cout << record[i][j][k] << " ";
- }
- cout << endl;
- }
- cout << endl;
- cout << endl;
- }
- }
- //该片段来自于http://www.codesnippet.cn/detail/1906201512891.html
来源: http://www.codesnippet.cn/detail/1906201512891.html