动态规划【C语言】01背包问题 |
您所在的位置：网站首页 › c语言finally › 动态规划【C语言】01背包问题 |
动态规划【C语言】01背包问题
|
目录
题目：输入格式输出格式输入样例输出样例
算法描述代码实现优化代码
题目：
有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。 第 i 件物品的体积是 vi，价值是 wi。求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。输出最大价值。 输入格式第一行两个整数，N，V，用空格隔开，分别表示物品数量和背包容积。 接下来有 N 行，每行两个整数 vi,wi，用空格隔开，分别表示第 i 件物品的体积和价值。 输出格式输出一个整数，表示最大价值。 输入样例 4 5 1 2 2 4 3 4 4 5 输出样例 8 算法描述参考 动态规划之01背包问题（最易理解的讲解）
“第 i 件物品应该放入背包中吗 ？” 代码实现 #include #define MAX(a,b) (a>b?a:b) int state[1001][1001];//存储状态 int main() { int N,V; scanf("%d%d",&N,&V); int v[1001],w[1001];//v[i]存储第 i 件物品的体积，w[i]第 i 件物品的价值 int i; for(i=1;i//对应于上表中从下到上 for(j=1;j if(j-v[i]//第 i 件物品体积允许，但还需要从价值上衡量 state[i][j]=MAX(state[i-1][j],state[i-1][j-v[i]]+w[i]); } }else{//状态初始化 if(j>=v[i]){ state[i][j]=w[i]; } } } } printf("%d",state[N][V]); return 0; } 优化代码 使用一维数组存储转换的状态 #include #define MAX(a,b) (a>b?a:b) int state[1001]; int main() { int N,V; scanf("%d%d",&N,&V); int v[1001],w[1001]; int i; for(i=1;i for(j=V;j>=v[i];j--){//上表中从右向左 state[j]=MAX(state[j],state[j-v[i]]+w[i]); } } printf("%d",state[V]); return 0; } |
【本文地址】
今日新闻 |
推荐新闻 |