开心的金明(0 1背包问题)

本文主要是介绍开心的金明(0 1背包问题)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

前两天谢了个01背包问题  第一次碰到 还不太熟悉  今天闲着又撸了一道题找找感觉

#include <iostream>
#include <cstdio>
#include <cstring>
#define max 30
using namespace std;
inline int max_value(int a,int b){return a>b?a:b;
}
int n,m,v[max],w[30],value[30002],i,j;
// v[i]第i件物品的价值 w[i]第i件物品的权重 value[i] 保存在有i元下能得到的最大满意度
int main()
{freopen("in.txt","r",stdin);while(scanf("%d%d",&n,&m)!=EOF){for(i=1;i<=m;i++)   scanf("%d%d",&v[i],&w[i]);memset(value,0,sizeof(value));for(i=1;i<=m;i++)for(j=n;j>=v[i];j--)value[j]=max_value(value[j],value[j-v[i]]+v[i]*w[i]);//这一句是关键  原式value[i][j]=max_value(value[i-1][j],value[i-1][j-v[i]]+v[i]*w[i]);//表示前i个物品在只有j元条件下所得到的的最大满意度//具体分为选第i个和不选第i个//但是如果j从最大的开始可以简写为value[j]=max_value(value[j],value[j-v[i]]+v[i]*w[i]);//为什么慢慢想printf("%d\n",value[n]);}return 0;
}

题目来源  sicily 1342

这篇关于开心的金明(0 1背包问题)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---