解题思路:其实就是01背包问题
注意事项:
参考代码:
#include <deque>
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <iterator>
#include <iomanip>
#include <numeric>
#include <sstream>
#include <string>
#include <cmath>
#include <string.h>
#define V 1001
using namespace std;
unsigned int f[101][V];//全局变量,自动初始化为0
unsigned int weight[101];
unsigned int value[101];
#define max(x,y) (x)>(y)?(x):(y)
int main()
{
int N,M;
cin>>M;//背包容量
cin>>N;//物品个数
for (int i=1;i<=N; i++)
{
cin>>weight[i]>>value[i];
}
for (int i=1; i<=N; i++)
for (int j=1; j<=M; j++)
{
if (weight[i]<=j)
{
f[i][j]=max(f[i-1][j],f[i-1][j-weight[i]]+value[i]);
}
else
f[i][j]=f[i-1][j];
}
cout<<f[N][M]<<endl;//输出最优解
}
0.0分
1 人评分
C语言程序设计教程(第三版)课后习题6.1 (C语言代码)浏览:664 |
众数问题 (C语言代码)浏览:821 |
WU-格式化数据输出 (C语言代码)浏览:1742 |
WU-判定字符位置 (C++代码)浏览:1395 |
C语言程序设计教程(第三版)课后习题1.6 (C语言代码)浏览:654 |
WU-C语言程序设计教程(第三版)课后习题12.1 (C++代码)浏览:919 |
回文数字 (C语言代码)浏览:2509 |
星期判断机 (C语言代码)浏览:859 |
sizeof的大作用 (C语言代码)浏览:1024 |
C语言程序设计教程(第三版)课后习题8.9 (C语言代码)浏览:498 |