求最优购买算法

Question

购物车的一个算法，大致流程是：

已知每种商品的价格、重要级（1到5，5是最重要）。在有限金额的情况下，可以买一种或者多种商品，每种商品数量1个，实现购买的积分（价格x重要级）最高。

举栗子：
A商品：价格 100元，重要级 3
B商品：价格 350，重要级 2
C商品：价格 800，重要级 5
D商品：价格 550，重要级 1

账户总金额：3000元

传入ABCD四种商品，算出买哪一种或者几种商品的积分最高。大家谁有算法的思路？谢谢！

Answer 1

这就是个背包问题，用动态规划来解决，嵌套两个循环，一个状态转移方程就能出结果，具体你可以看看这篇文章01背包问题，贴一下他的代码：

#include<iostream>
#include<algorithm>
using namespace std;

int main()
{
    const int N = 6;                     //物品个数
    const int V = 10;                    //背包体积
    int C[N + 1] = { -1,5,6,5,1,19,7 };  //第i个物品的体积（下标从1开始）
    int W[N + 1] = { -1,2,3,1,4,6,5 };   //第i个物品的价值
    int F[N + 1][V + 1] = { 0 };         //状态

    for (int i = 1; i <= N; i++)  //对于第i个物品
        for (int v = 0; v <= V; v++)
        {
            F[i][v] = F[i - 1][v];  //第i个不放
            if (v - C[i] >= 0 && F[i][v] < F[i - 1][v - C[i]] + W[i])  //如果比它大，再放第i个
                F[i][v] = F[i - 1][v - C[i]] + W[i];
        }

    cout << "最大价值是：" << F[N][V] << endl;  //9

    return 0;
}

希望能帮助到你。