解题思路:其实就是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 人评分
Tom数 (C语言代码)浏览:736 |
C语言程序设计教程(第三版)课后习题8.9 (C++代码)浏览:853 |
C语言训练-字符串正反连接 (C语言代码)浏览:692 |
C语言程序设计教程(第三版)课后习题6.9 (C语言代码)浏览:703 |
C语言程序设计教程(第三版)课后习题5.7 (C语言代码)浏览:939 |
C语言程序设计教程(第三版)课后习题8.6 (C语言代码)浏览:581 |
C语言训练-计算t=1+1/2+1/3+...+1/n (C语言代码)浏览:868 |
C语言程序设计教程(第三版)课后习题7.1 (C语言代码)浏览:730 |
母牛的故事 (C语言代码)浏览:435 |
这可能是一个假的冒泡法浏览:989 |