AcWing 12. 背包问题求具体方案

2021-01-26 09:12

阅读：765

标签：mes bsp class turn 状态 color 从后往前背包问题 code

//f[i][j]=max(f[i-1][j],f[i-1][j-v[i]]+w[i]) 
#include using namespace std;
const int N = 1010;
int n, m;
int v[N], w[N];
int f[N][N];
int main() {
    cin >> n >> m;
    for (int i = 1; i > v[i] >> w[i];
    for (int i = n; i >= 1; i -- )//最小字典序，从前往后推，那么做dp的时候，从后往前 
        for (int j = 0; j //由于状态是两维的，所以循环顺序无所谓 
            f[i][j] = f[i + 1][j];
            if (j >= v[i]) f[i][j] = max(f[i][j], f[i + 1][j - v[i]] + w[i]);
        }
    //f[1][m]是最大价值 
    int j = m;
    for (int i = 1; i //依次看每个物品能不能选 
            //保证后面大于等于0 
        if (j >= v[i] && f[i][j] == f[i + 1][j - v[i]] + w[i]) {//只要可以选，就必选 
            cout ‘ ‘;
            j -= v[i];
        }
    return 0;
}

标签：mes bsp class turn 状态 color 从后往前背包问题 code

原文地址：https://www.cnblogs.com/QingyuYYYYY/p/11992995.html

上一篇：vue-cli3搭建的vue项目中使用jquery

下一篇：Win10提示“无法打开此计算机上的组策略对象”如何解决

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：AcWing 12. 背包问题求具体方案
文章链接：http://soscw.com/index.php/essay/47197.html

亲，登录后才可以留言！

AcWing 12. 背包问题求具体方案

评论

热门文章

推荐文章

最新文章

置顶文章