# Q：我如何动态地处理这个任务？[关闭]

I think this problem is a good beginner problem to think in a tabular fashion. I think I've managed to get the gist, but still not very clear. My code doesn't seem to do the job. Here's the question:

The question is to maximise the number of pieces such that the total length is equal to N.

``````Sample input:
5(total length) 5 3 2(individual pieces length)
output:
The answer could be 1(if you select 5) or 2(in the case of 3+2)
``````

After a bit of thinking I came up with this:

``````#include<iostream>
#include<algorithm>
using namespace std;

int main()
{
int total_length, individual_lengths[3];
cin >> total_length;
for(int i=1;i<=3;i++)
cin >> individual_lengths[i];

int dp[total_length+1];
dp[0]=0;

for(int i=1;i<=total_length;i++)
{
for(int k=1;k<=3;k++)
if(individual_lengths[k]<=i)
dp[i]=max(dp[i-1], dp[i-individual_lengths[k]]+1);
}
cout << dp[total_length];
}
``````

dp function initialisation: let dp[i] be total number of pieces for the length i of the ribbon

dp base case: if i is zero, dp[0](total number of pieces if the length is zero) would be 0. Therefore, dp[0] = 0

recurrence relation: if the length current piece a[k](1<=k<=3) <= total_length being considered, dp[i] = max(dp[i-1], dp[i-a[k]] + 1)

Is my flow of thought formulating this task correct? Any suggestions toward improvement(possibly restricted on dynamic programming approach, not brute force) would be of help.

``````Sample input:
5(total length) 5 3 2(individual pieces length)
output:
The answer could be 1(if you select 5) or 2(in the case of 3+2)
``````

``````#include<iostream>
#include<algorithm>
using namespace std;

int main()
{
int total_length, individual_lengths[3];
cin >> total_length;
for(int i=1;i<=3;i++)
cin >> individual_lengths[i];

int dp[total_length+1];
dp[0]=0;

for(int i=1;i<=total_length;i++)
{
for(int k=1;k<=3;k++)
if(individual_lengths[k]<=i)
dp[i]=max(dp[i-1], dp[i-individual_lengths[k]]+1);
}
cout << dp[total_length];
}
``````

DP函数初始化：让DP [我]是为我带的长度总件数

DP的基本情况：如果我是零，DP [ 0 ]（总件数，如果长度为零）是0。因此，DP [ 0 ] = 0

EDIT**

Lets say that len=13, a=2, b=4, and c=5.

``````for(int i=1;i<=len;i++)
{
for(int k=1;k<=3;k++)
if(a[k]<=i)
dp[i]=max(dp[i-1], dp[i-a[k]]+1);
}
//i=1,k=1,2,3->skip
//i=2,k=1->dp[2]=max(dp[i-1],dp[i-a[k]+1])
//here is an issue!  dp[i-1] or dp[2-1] has not been assigned!

//so lets try if all dp values are initialized as 0, continueing from before
//i=2,k=1->dp[2]=max(0,0) //because dp[/*i-1*//*2-1*/1] = 0, and dp[/*1+i-a[k]*//*1+2-a[1]*//*3-2*/1] = 0
//i=2,k=2,3->skip
//i=3,k=1->.......
``````

essentially, from what I can tell, you'd just be comparing 0's. ** I would just do

``````int count = static_cast<int>(len/a);
len%=a;
for (int sum = count*a; sum != len; sum-=a)
{
if (!(sum+c<len || sum+b<len))
count--;
sum+=sum+c<len?c:sum+b<len?b:0;
}
``````

``````for(int i=1;i<=len;i++)
{
for(int k=1;k<=3;k++)
if(a[k]<=i)
dp[i]=max(dp[i-1], dp[i-a[k]]+1);
}
//i=1,k=1,2,3->skip
//i=2,k=1->dp[2]=max(dp[i-1],dp[i-a[k]+1])
//here is an issue!  dp[i-1] or dp[2-1] has not been assigned!

//so lets try if all dp values are initialized as 0, continueing from before
//i=2,k=1->dp[2]=max(0,0) //because dp[/*i-1*//*2-1*/1] = 0, and dp[/*1+i-a[k]*//*1+2-a[1]*//*3-2*/1] = 0
//i=2,k=2,3->skip
//i=3,k=1->.......
``````

essentially, from what I can tell, you'd just be comparing 0's. ** I would just do

``````int count = static_cast<int>(len/a);
len%=a;
for (int sum = count*a; sum != len; sum-=a)
{
if (!(sum+c<len || sum+b<len))
count--;
sum+=sum+c<len?c:sum+b<len?b:0;
}
``````
c++  dynamic-programming