rqnoj-140-分配时间-分组背包有关问题
rqnoj-140-分配时间-分组背包问题
分组背包问题。
分组背包问题的算法流程:
for 每个组
for 每个状态
for 组里的每个成员
#include<string.h> #include<stdio.h> #include<iostream> #include<algorithm> using namespace std; int a[1001]; int dp[10001]; int main() { int t,n,vs,i,j; while(~scanf("%d%d%d",&t,&n,&vs)) { while(n--) { for(i=1;i<=t;i++)scanf("%d",&a[i]); for(i=t;i>vs;i--) { for(j=1;i-vs-j>=0;j++) { dp[i]=max(dp[i],dp[i-vs-j]+a[j]); } } } cout<<dp[t]<<endl; } return 0; }