1175金明的预算方案(dp动态规划，一维数组）

解题思路:

注意事项:

参考代码:

#include<iostream>

using namespace std;

#define MAX  10100

int N, m;

int dp[MAX];

int arr[MAX];//存选择了第 i 件物品时的花费

int brr[MAX];//存选择了第 i 件物品时的 价值与钱的乘积

int v, p, q;

int k = 1;//记录当前选择了几件主商品

int main()

{

cin >> N >> m;

for (int i = 1; i <= m; i++)

{

cin >> v >> p >> q;

if (q == 0)//表示是主商品

{

arr[k] = v;

brr[k] = p * v;

k++;

}

else//表示是副商品，我们就将它的钱和价值算到第一件主商品中

{

arr[1] += v;

brr[1] += v * p;

}

}

for (int i = 1; i <= m; i++)

{

for (int j = N; j >= arr[i]; j--)

{

dp[j] = max(dp[j], dp[j - arr[i]] + brr[i]);

}

}

cout << dp[N];

return 0;

}