找到你要的答案

Q:How do I approach this task thinking dynamically? [closed]

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.

我认为这个问题是一个很好的初学者问题。我想我已经明白了要点,但还是不太清楚。我的代码似乎不做这项工作。以下是问题:

问题是使工件的最大化,使总长度等于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)

经过一点思考,我想出了这个:

#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

递推关系:如果长度电流片[ k ](1 & lt;= k <;<;= = 3)total_length正在考虑,DP [我] = max(DP [·],[一] [ K DP ] + 1)

我的思维流程是否正确?任何改进的建议(可能限制在动态编程方法,而不是蛮力)将是有帮助的。

answer1: 回答1:

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;
}

编辑* *

可以说,len = 13,= 2,B = 4,和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;
}
c++  dynamic-programming